Boyer-Moore Voting

Problem

Find the element that appears more than [n/2] times in an array (guaranteed to exist).

Idea

• Treat each element as a "vote".
• +1 if it matches the current candidate.
• -1 if it doesn't.
• If votes reach 0, switch candidate to the current element.

Steps

1. Initialize candidate = None, count = 0.
2. For each element:
   • If count == 0: set candidate = element.
   • If element == candidate: count += 1 else count -= 1.
3. Return candidate.

Complexity

• Time: O(n) – single pass
• Space: O(1) – constant space

Example

Array: [2, 2, 1, 1, 1, 2, 2]
Final candidate after cancellations = 2.

Code

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