The problem
Find the value that appears more than half the time.
Input: [2, 2, 1, 1, 1, 2, 2] Output: 2
Picture it
Picture an election where every vote for someone else cancels one vote for the current leader. The leader changes when their count drops to zero. A true majority can never be fully cancelled, so it’s the one left standing.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Boyer–Moore voting: O(n) time, O(1) memory.
Python solution
def majority(votes):
candidate, count = None, 0
for v in votes:
if count == 0:
candidate = v
count += 1 if v == candidate else -1
return candidateIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.