Majority Element: Find the Element That Appears More Than N/2 Times

Preparing for coding interviews? This blog series shall help you practice some of the most commonly asked data structure problems in top tech companies.

Each post will include:

• A clear explanation of the problem

• A simple and efficient solution (in C)

• Sample input/output

• Common mistakes to avoid

Let’s get started with a classic one — Majority Element.

📌 Problem Description

"Given an integer array of size N, return the majority element. A majority element is one that appears more than floor(N/2) times. You can assume the array is non-empty and always contains a majority element."

📝 Note:

• There can be only one majority element, since two elements cannot both appear more than ⌊N/2⌋ times in the same array.

• If no such element exists, then technically there is no majority — but this question guarantees that one always exists.

🧠 Problem Constraints

• 1 ≤ N ≤ 10⁶

• 1 ≤ A[i] ≤ 10⁹

• Array is non-empty, and a majority element always exists

🧪 Sample Input

Input:  A = [2, 1, 2]
Output: 2

Explanation: The number 2 occurs twice, which is more than floor(3/2) = 1. Hence, 2 is the majority element.

💡 Approach: Boyer-Moore Voting Algorithm (Optimized)

This algorithm solves the problem in:

• Time Complexity: O(N)

• Space Complexity: O(1)

✅ Idea to Solve:

We use a voting mechanism:

• Start with the first element as candidate and count = 1.

• If the current element is the same as the candidate, increase the count.

• If it's different, decrease the count.

• If the count drops to 0, replace the candidate with the current element.

Since the problem guarantees a majority element, the final candidate will be correct.

🔧 C Code

#include <stdio.h>
int majorityElement(const int* A, int n) {
    int candidate = A[0];
    int count = 1;

    for (int i = 1; i < n; i++) {
        if (A[i] == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                candidate = A[i];
                count = 1;
            }
        }
    }
    return candidate;
}

int main() {
    int A[] = {2, 1, 2};
    int n = sizeof(A) / sizeof(A[0]);
    int result = majorityElement(A, n);
    printf("Majority Element: %d\n", result);
    return 0;
}

🔍 Example

Let’s consider A = [2, 1, 2]

→ Final candidate = 2 ✅

---

⚠️ Common Mistakes

1. Not understanding the majority condition: It’s not just the most frequent, it must be \> N/2.

2. Sorting approach: While it works (O(N log N)), it’s not optimal for big inputs (N = 10^6).

3. Using a hash map: Takes extra space O(N). Interviewers often expect O(1) space solutions.

🏢 Asked In:

• Amazon – Online assessment, SDE-1

• Google – Technical phone round

• Adobe – DS round

• Microsoft – Initial coding round

📚 References

🧠 Algorithm

• Boyer-Moore Voting Algorithm - Wikipedia

• LeetCode Problem #169: Majority Element

🏢 Asked In (Company-Specific Sources)

• Amazon
  GeeksforGeeks - Amazon Interview Experience
  “Find the majority element in an array. An element that appears more than n/2 times.”

• Google
  LeetCode Discuss - Google Interview Experience
  “One of the questions asked in the phone screen: Given an array, return the majority element (more than n/2).”

• Adobe
  InterviewBit - Adobe Interview Questions
  Common questions include finding elements occurring more than n/2 times.

• Microsoft
  GeeksforGeeks - Microsoft Interview Experience
  “Majority element problem was asked in one of the coding rounds.”

🧵 Wrap Up

This problem is a classic favorite for interviews, especially for companies that value optimized thinking. Remember: interviewers love candidates who balance performance and clarity.

📌 Next Up: Find the First Non-Repeating Character in a String (Amazon, Meta)