Majority Element

The machine must return the value that appears more than n/2 times in an array; the majority is guaranteed to exist. The insight is Boyer–Moore voting: pair up different elements and cancel them. A majority element survives every pairing, because it outnumbers everything else combined. One counter, one candidate, no hash map.

def majority_element(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

Steps: (1) walk the array with a candidate and a counter, (2) when the counter hits zero, adopt the current value as the new candidate, (3) increment for a match, decrement otherwise. The surviving candidate is the majority.

Time is O(n), one pass. Space is O(1).

Trickiest edge case: the algorithm returns a candidate even when no majority exists — it works here only because the problem guarantees one. Verify the guarantee before trusting the result in production. For [2,2,1,1,1,2,2], the counter hovers near zero but the candidate is never fully cancelled; that is exactly why the guarantee matters.