Majority Element (n/2)

Majority Element asks you to find the value that appears more than half the time in an array. The clever solution, Boyer-Moore voting, finds it in one pass using just two variables — no extra memory at all.

The slow way first

The obvious idea: count every value. Use a hash map from value to its frequency, scan once filling it in, then return whichever key has a count above n / 2. That works and it is O(n) time — but it costs O(n) extra space for the map.

The question to ask: can I find the winner without remembering every count? Because the majority element appears more than half the time, it outnumbers everything else combined. That imbalance is something we can exploit with a single counter.

The idea: let votes cancel out

Keep one candidate and a running count. Walk the array casting votes:

• If count is 0, the candidate is up for grabs — adopt the current element and set count = 1.
• If the current element matches the candidate, it is a supporting vote: count += 1.
• If it differs, it is an opposing vote that cancels one: count -= 1.

Pair off every minority element against a majority element and they annihilate each other. Since the majority element has more than half the votes, at least one of it always survives — whatever the candidate is at the end is the answer.

The key insight: we are not tracking the true count of any value — count just measures how far ahead the current candidate is. When it drops to 0 the lead is gone and a fresh candidate steps in.

Walk through it

Step through the animation. The pointer i scans left to right. Watch candidate and count underneath. Twice the count crashes to 0 and a new candidate is adopted (first 1, then back to 2), but 2 is the only value with enough votes to survive — so it wins. The final step verifies the survivor really appears more than half the time.

Pseudocode

candidate = none, count = 0
for each num in nums:
    if count == 0:
        candidate = num          # empty seat — adopt this element
        count = 1
    else if num == candidate:
        count = count + 1        # a supporting vote
    else:
        count = count - 1        # an opposing vote cancels one
return candidate                  # the survivor (majority is guaranteed)

The Python solution

def majority_element(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    # majority is guaranteed to exist
    return candidate

• candidate holds whoever is currently winning; count is their lead, not a true tally.
• When count == 0 the lead has evaporated, so the current num claims the seat and the lead resets to 1.
• elif num == candidate adds a supporting vote, raising the lead.
• The else branch is an opposing vote that cancels one unit of the lead.
• After the loop, candidate is the value that outlasted every cancellation — the majority element.

Complexity

Both approaches are O(n) time, but Boyer-Moore wins on space: it uses just two variables instead of a whole map. That constant-space trick is what makes it a favorite interview answer.

When this pattern shows up

Practice