Majority Element

The definition of a majority is a threshold: a value appears more than floor(n / 2) times. The most direct reading of that definition is to count everything and then pick the value that clears the bar. One pass fills a hash map with the tally of every value; a second pass over the map finds the count greater than n // 2. Because the statement guarantees a majority exists, the map is guaranteed to contain the winner — the unreachable return is only for the type checker.

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        n = len(nums)
        counts = {}
        for num in nums:
            counts[num] = counts.get(num, 0) + 1
        for num, count in counts.items():
            if count > n // 2:
                return num
        return -1  # unreachable: the statement guarantees a majority

Why it still costs O(n) space: the running time is already optimal at O(n) — any correct solution must at least read every element once — so the only thing this approach wastes is memory. In the worst case the array holds n distinct values and the map grows to n entries, so the space bill is O(n). A micro-optimization is easy: check the threshold inside the first loop and return the instant some count crosses it, since floor(n / 2) is fixed once n is known. But the map stays the same size, and that extra memory is exactly what the next solution eliminates.

Boyer-Moore keeps exactly two variables: a candidate and a lead (the count). Walk the array once. If the lead is 0, the current value claims the candidate slot with a lead of 1. Otherwise a read that matches the candidate raises the lead by 1, and any different read lowers it by 1 — each rival vote cancelling one candidate vote. When the lead returns to 0, an equal-size block of rivals has cancelled the candidate block exactly, so the whole cancelled prefix is forgotten and the next read restarts the race.

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = None
        count = 0
        for num in nums:
            if count == 0:          # no lead: current value claims the slot
                candidate = num
                count = 1
            elif num == candidate:  # same team: extend the lead
                count += 1
            else:                   # rival vote: cancels one candidate vote
                count -= 1
        return candidate

Why the majority is guaranteed to win: write M for the true majority. It appears more than floor(n / 2) times, so its votes outnumber all other votes combined across the entire array. Every time the lead hits 0, the prefix scanned since the last claim held exactly as many candidate votes as rival votes — no value owned more than half of that prefix — and cancelling such a tied prefix cannot reduce M’s advantage in the rest of the array. The votes still standing at the end are therefore M’s unpaired surplus, and the final candidate is exactly that surplus. The lead-0 moments in the traces below are these equal-block cancellations happening in real time.

Why it is optimal: the single pass reads each of n elements once for O(n) time — matching the hash map — but keeps only two integers, so space is O(1). Time cannot improve below O(n) because every element must be examined, and space cannot improve below O(1), so this solution is optimal on both axes.

Watch the lead on the file example, nums = [2, 2, 1, 1, 1, 2, 2] — the block of three 1s first cancels the 2 lead to 0, then a 1 claims the slot, then a 2 wipes that lead and rebinds. The two depose moments are the entire mechanism:

Then a shorter second look, nums = [3, 2, 3] — a majority that loses its whole lead mid-array and still wins on its surplus: