Majority Element

This is one of those questions that looks easy. You count things. You find the winner. Done. But the interviewer is not really testing counting. They want to see if you can do it without using extra memory. So the real test here is space. Can you find the most common element while using almost no extra space? Let us talk through it.

🗳️ The Problem

You are given an array of numbers. One element appears more than half the time. We call this the majority element. The majority element is the value that shows up more than n/2 times. Here n is the size of the array. The problem promises us that such an element always exists. So we do not have to worry about the case where there is no winner.

Here is what the input and output look like:

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

Explanation: The array has 7 elements. The value 2 appears 4 times.
4 is more than 7/2, so 2 is the majority element.

🧮 The Simple Approach: Count Everything

The first idea most people get is to count. Go through the array. Keep a tally of how many times each number appears. Then pick the number whose count is more than n/2.

To keep the counts, we use a hash map. A hash map is a small table that stores each number together with how many times we have seen it. So you walk the array once. For every number you add one to its count in the map.

This works fine. It runs in O(n) time because you look at each element once. But there is a catch. You are storing a count for every different number. So in the worst case the map holds many entries. That costs O(n) extra space. The interviewer will usually nod and then ask the real question. “Can you do this without the extra map?” That is where the better idea comes in.

🤝 The Optimal Approach: Boyer-Moore Voting

Here is the clever trick. It is called the Boyer-Moore voting algorithm. The Boyer-Moore voting algorithm finds the majority element using just one candidate value and one counter. So no map at all.

Think of it like an election in a room. Imagine people holding signs with their number. Now pair up people who hold different numbers, and make both of them leave. Each pair that leaves removes one majority vote and one non-majority vote. So the pairs cancel out. The majority element appears more than half the time. So it has more people than everyone else put together. No matter how many pairs cancel, at least one person from the majority group is always left standing at the end.

We turn that idea into code with two variables. We keep a candidate, which is our current guess for the winner. And we keep a count, which is how strong that guess is right now. See how it flows:

• When count is zero, we have no guess. So we pick the current number as the new candidate.
• When the current number is the same as the candidate, that is a supporting vote. So we add one to count.
• When the current number is different, that is an opposing vote. So we subtract one from count. This is the “pair cancels out” step.

By the end, the candidate left standing is the majority element.

Steps to find the majority element

1. Start with count set to 0 and no candidate yet.
2. Walk through the array one number at a time.
3. If count is 0, set the current number as the candidate.
4. If the current number equals the candidate, add 1 to count.
5. Otherwise, subtract 1 from count.
6. After the loop, the candidate is your answer.

#include <stdio.h>

// Boyer-Moore voting: one candidate, one count
int majorityElement(int nums[], int n) {
    // count starts at 0, so the first element always overwrites this
    int candidate = 0;
    int count = 0;

    for (int i = 0; i < n; i++) {
        // No active guess, so adopt the current number
        if (count == 0) {
            candidate = nums[i];
        }
        // Supporting vote adds 1, opposing vote subtracts 1
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

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

Majority element: 2

#include <iostream>
#include <vector>
using namespace std;

// Boyer-Moore voting: one candidate, one count
int majorityElement(vector<int>& nums) {
    // count starts at 0, so the first element always overwrites this
    int candidate = 0;
    int count = 0;

    for (int num : nums) {
        // No active guess, so adopt the current number
        if (count == 0) {
            candidate = num;
        }
        // Supporting vote adds 1, opposing vote subtracts 1
        if (num == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

int main() {
    vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
    cout << "Majority element: " << majorityElement(nums) << endl;
    return 0;
}

Majority element: 2

public class MajorityElement {

    // Boyer-Moore voting: one candidate, one count
    static int majorityElement(int[] nums) {
        // count starts at 0, so the first element always overwrites this
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            // No active guess, so adopt the current number
            if (count == 0) {
                candidate = num;
            }
            // Supporting vote adds 1, opposing vote subtracts 1
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("Majority element: " + majorityElement(nums));
    }
}

Majority element: 2

# Boyer-Moore voting: one candidate, one count
def majority_element(nums):
    candidate = None
    count = 0

    for num in nums:
        # No active guess, so adopt the current number
        if count == 0:
            candidate = num
        # Supporting vote adds 1, opposing vote subtracts 1
        if num == candidate:
            count += 1
        else:
            count -= 1

    return candidate


nums = [2, 2, 1, 1, 1, 2, 2]
print("Majority element:", majority_element(nums))

Majority element: 2

// Boyer-Moore voting: one candidate, one count
function majorityElement(nums) {
  let candidate = null;
  let count = 0;

  for (const num of nums) {
    // No active guess, so adopt the current number
    if (count === 0) {
      candidate = num;
    }
    // Supporting vote adds 1, opposing vote subtracts 1
    if (num === candidate) {
      count += 1;
    } else {
      count -= 1;
    }
  }
  return candidate;
}

const nums = [2, 2, 1, 1, 1, 2, 2];
console.log("Majority element:", majorityElement(nums));

Majority element: 2

⏱️ Time and Space Complexity

Both methods look at every element once. So the time is the same. The big difference is space. The map method stores counts for many numbers. The voting method stores just two variables. See the comparison:

🧩 Key Takeaways

• ✅ The majority element appears more than n/2 times, and this problem guarantees one exists.
• ✅ The hash map method is simple and runs in O(n) time, but it costs O(n) extra space.
• ✅ The Boyer-Moore voting algorithm gives the answer in O(n) time using only O(1) space.
• ✅ The idea is that opposing votes cancel in pairs, so the majority value is always left standing.
• ✅ Without a guaranteed majority, add a verification pass to confirm the candidate is real.

🚀 What’s Next?

• Two Sum
• Group Anagrams