Majority Element (LeetCode 169)

The problem

You get an array nums of length n. One value, the majority element, appears more than n / 2 times. It is guaranteed to exist. Return it.

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

2 appears four times out of seven, which is more than half.

How to think about it

Start with brute force. For each value, count how often it appears by scanning the array: O(n²). Sorting is better: the majority element must sit at index n // 2 of the sorted array, since it fills more than half. That’s O(n log n).

The natural hash-map answer. Count every value with a dictionary and return the one whose count exceeds n / 2. That’s O(n) time and O(n) space, and it’s what this lesson trains you to reach for first. The follow-up asks: can you do it in O(1) space?

The key insight: pair off different values and the majority survives. Imagine every element as a vote. Cancel out one vote for the majority against one vote for anything else. Since the majority has more than half of all votes, it can’t be fully cancelled; there is always at least one of its votes left at the end. Boyer–Moore voting does this cancelling in a single pass: keep a cand and a count. A matching element adds one; a different one subtracts one. When count hits zero, the next element becomes the new candidate.

Why a “wrong” candidate is harmless. A candidate that isn’t the majority gets cancelled before the end, because the majority’s surplus outlasts it. Any prefix where count drops to zero has its votes paired off evenly, so the majority still holds more than half of what remains.

Which pattern is this? Counting, with Boyer–Moore as the O(1)-space upgrade of the frequency map. The tell is “more than half” (or “more than n/k”).

Approach

1. Start with count = 0 and no candidate.
2. For each x: if count is 0, make x the candidate.
3. Add one to count if x equals the candidate, otherwise subtract one.
4. After the pass, the candidate is the majority element.

Solution

def majority_element(nums):
    count = 0; cand = None
    for x in nums:
        if count == 0: cand = x                  # all earlier votes cancelled out
        count += 1 if x == cand else -1          # support or cancel one vote
    return cand
# majority_element([2,2,1,1,1,2,2]) -> 2

Dry run

On [2, 2, 1, 1, 1, 2, 2], showing values after each element:

The candidate briefly becomes 1, but the last 2 takes it back, and the function returns 2.

Complexity

• Time: O(n). One pass, constant work per element.
• Space: O(1). Two variables, compared with O(n) for the dictionary count.

Edge cases and pitfalls

• Single element: [5] returns 5.
• No guaranteed majority: Boyer–Moore always returns some candidate. If the problem doesn’t promise a majority, do a second pass to count the candidate and confirm it’s more than n / 2.
• count is not the frequency. At the end, count is only the surplus. Don’t report it as the number of occurrences.
• “More than n/3” variant (LeetCode 229): keep two candidates and two counters, then verify both.

Related problems

• Contains Duplicate (LeetCode 217): another “what does the frequency look like?” question answered with a set.
• Top K Frequent Elements (LeetCode 347): count frequencies and pick the k largest.
• Single Number (LeetCode 136): another O(1)-space trick where pairs cancel, this time with XOR.