Majority Element

Majority Element

What is this problem about?

The Majority Element problem provides an array of integers of size N. Your task is to find the "majority element", which is defined as the element that appears strictly more than ⌊N / 2⌋ times. You may assume that the array is non-empty and the majority element always exists in the array.

Why is this asked in interviews?

This is one of the most frequently asked introductory algorithm questions. While a Hash Map solution is trivial, interviewers ask it to test a candidate's algorithmic breadth. It provides a perfect runway to discuss Space vs. Time complexity tradeoffs. It is specifically designed to see if a candidate is aware of the brilliant, $O(1)$ space Boyer-Moore Voting Algorithm.

Algorithmic pattern used

While you can use a Hash Table to count frequencies ($O(N)$ time, $O(N)$ space) or Sorting ($O(N \log N)$ time, $O(1)$ space), the most optimal pattern is the Boyer-Moore Voting Algorithm ($O(N)$ time, $O(1)$ space). The algorithm maintains a candidate and a count. When you see the candidate, you increment the count. When you see a different number, you decrement the count. If the count hits 0, you assign the current number as the new candidate. Because the majority element appears more than half the time, its net count will mathematically always remain positive at the end.

Example explanation

Array: [2, 2, 1, 1, 1, 2, 2]

• num = 2: count = 0. Assign candidate = 2. count = 1.
• num = 2: Matches! count = 2.
• num = 1: Mismatch. count = 1.
• num = 1: Mismatch. count = 0.
• num = 1: count = 0. Assign candidate = 1. count = 1.
• num = 2: Mismatch. count = 0.
• num = 2: count = 0. Assign candidate = 2. count = 1. End of array. The final candidate is 2. Since 2 appears 4 times out of 7, it is indeed the majority element.

Common mistakes candidates make

Candidates often jump straight to the Hash Map solution and consider the problem solved. If you do this without mentioning the $O(1)$ space optimization, you might miss out on a "Strong Hire" rating. Another mistake when implementing Boyer-Moore is failing to assign the new candidate before processing the element, or getting the increment/decrement logic jumbled when count == 0.

Interview preparation tip

For the Majority Element interview question, always verbally acknowledge the Hash Map solution first to show you know the basics, but immediately offer the Boyer-Moore Voting Algorithm as an optimization. Think of it as a battle: the majority element's "votes" will always outnumber the combined "votes" of every other element in the array, ensuring it's the last one standing.