169. Majority Element

Problem¶

Given a non-empty array where one value appears more than half the time, return that value.

• Example:

  nums = [2,2,1,1,1,2,2] -> 2
  because 2 appears 4 times out of 7 (> 7/2)
  

Key trick¶

Use Boyer-Moore voting.

• Keep a candidate and a count.
• Same value increases count.
• Different value decreases count.
• Pairs of different values cancel, so the true majority survives.

Trap¶

• Forgetting that the guarantee matters: without it, Boyer-Moore may need a final verification pass.
• Updating the candidate in the wrong order when count == 0.
• Overusing a hash map when the follow-up asks for \(O(1)\) space.

Why is it interesting?¶

It looks like a counting problem, but the best solution is a greedy cancellation idea.

• It turns a frequency task into a neat invariant-based scan.
• It is a classic example of getting \(O(n)\) time and \(O(1)\) space.

Python solution¶

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        # Boyer-Moore voting:
        # cancel one occurrence of the candidate with one different value.
        cand, cnt = None, 0

        for x in nums:
            if x == cand:
                cnt += 1
            elif cnt == 0:
                cand, cnt = x, 1
            else:
                cnt -= 1

        # Valid because the problem guarantees a majority element exists.
        return cand

• Complexity:
  • Time: \(O(n)\)
  • Space: \(O(1)\)

Comment on my solution¶

Your solution is correct and already the ideal interview answer.

• It uses the right algorithm: Boyer-Moore.
• It meets the follow-up: \(O(n)\) time and \(O(1)\) space.
• Your comment about canceling pairs is the key insight.

Tiny style note:

• Many people check count == 0 first, then compare with candidate; it reads a bit more directly, but your version is still correct.

# WORKS
class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        cand = None # current potential majority element
        count = 0

        for x in nums:
            if x == cand:
                count += 1
            elif count == 0:
                cand = x
                count = 1
            else:
                # cancel pair of distinct elements
                count -= 1

        return cand