"""
Exercise 1: Majority Element (LeetCode 169)

Return the element that appears more than n // 2 times (it always exists).
First solve it with a dict of counts (O(n) space). Then, if you want a
challenge, try Boyer-Moore voting (O(1) space): keep a candidate and a
counter; +1 when you see the candidate, -1 otherwise, switch when it hits 0.

  majority_element([3, 2, 3])               -> 3
  majority_element([2, 2, 1, 1, 1, 2, 2])   -> 2
"""

def majority_element(nums):
    # TODO
    pass


# --- self-check: do not modify below this line ---
cases = [([3, 2, 3], 3), ([2, 2, 1, 1, 1, 2, 2], 2), ([7], 7), ([1, 1, 2], 1), ([5, 6, 6, 5, 6], 6)]
ok = True
for nums, want in cases:
    got = majority_element(nums)
    print(nums, "->", got, "expected", want)
    ok = ok and got == want
print("PASS" if ok else "FAIL")