Majority Element II

Boyer-Moore with two seats — cancellation in threes

time O(n)space O(1)

More than n/3 of the cells is a bar at most two values can clear at once, so the whole problem fits in two candidate seats and two counters. Scan once: a value matching a seat adds a vote, and a value matching neither burns one vote from BOTH seats. That triple cancellation is the whole idea — it destroys votes three at a time, and a value owning more than a third of the cells cannot be fully paired away. Surviving is necessary but not sufficient, so a second counting pass confirms each seat holder before it is returned.

Details

Animated on: nums = [1, 2, 2, 3, 2, 1, 1] — return every value appearing more than floor(n/3) times.

Problem:Majority Element IIMedium

Boyer-Moore with two seats — cancellation in threes

step 1 / 12

[0]

[1]

[2]

[3]

[4]

[5]

[6]

n = 7, so a value has to appear more than floor(7/3) = 2 times to qualify. At most two values can ever clear that bar — three of them would already need more than 7 cells — so two candidate seats and two vote counters are enough to survive the whole scan.

i=0· arr[0] = 1

Pseudocode

1FUNCTION majorityElementII(nums)
2  c1 <- NONE
3  c2 <- NONE
4  k1 <- 0
5  k2 <- 0
6  FOR i <- 0 TO LENGTH(nums) - 1
7    IF nums[i] = c1 THEN k1 <- k1 + 1
8    ELSE IF nums[i] = c2 THEN k2 <- k2 + 1
9    ELSE IF k1 = 0 THEN c1 <- nums[i], k1 <- 1
10    ELSE IF k2 = 0 THEN c2 <- nums[i], k2 <- 1
11    ELSE k1 <- k1 - 1, k2 <- k2 - 1
12  RETURN EACH c IN c1, c2 WITH COUNT(nums, c) > LENGTH(nums) / 3

← / → step · space play · Home restart

Every step in words

Show all 12 steps

n = 7, so a value has to appear more than floor(7/3) = 2 times to qualify. At most two values can ever clear that bar — three of them would already need more than 7 cells — so two candidate seats and two vote counters are enough to survive the whole scan.
nums[0] = 1 matches neither seat, but seat 1 is unclaimed (k1 = 0), so 1 moves in instead of cancelling: c1 = 1, k1 = 1.
nums[1] = 2 is not c1 = 1, and seat 2 is still unclaimed (k2 = 0). Cancelling here would be wasteful when we are allowed to track two survivors, so 2 takes seat 2: c2 = 2, k2 = 1.
nums[2] = 2 matches the value in seat 2, so it defends that seat: k2 goes 1 -> 2.
nums[3] = 3 matches neither seat and both seats are defended (k1 = 1, k2 = 2), so this one 3 annihilates one vote from EACH: k1 -> 0, k2 -> 1. Three different values die together, so a value holding at most a third of the cells can always be paired away.
nums[4] = 2 matches the value in seat 2, so it defends that seat: k2 goes 1 -> 2.
nums[5] = 1 matches the value already in seat 1, so it defends that seat: k1 goes 0 -> 1 — the seat was at zero votes but was never handed away, so 1 keeps it for free.
nums[6] = 1 matches the value already in seat 1, so it defends that seat: k1 goes 1 -> 2.
Scan over: seat 1 holds 1 (k1 = 2), seat 2 holds 2 (k2 = 2). Surviving the cancellation proves nothing on its own — with no qualifying value at all, two arbitrary numbers still end up seated. So count both for real in a second pass.
1 really appears 3 times at indices 0, 5, 6, and 3 > 7/3 = 2.33, so 1 is a genuine > n/3 element.
2 really appears 3 times at indices 1, 2, 4, and 3 > 7/3 = 2.33, so 2 is a genuine > n/3 element.
Answer: [1, 2]. 3 appears only 1 time — too thin to ever hold a seat, which is exactly what the cancellation pass filtered out in one sweep of O(1) memory.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Majority Element II in the editor All Arrays problems Back to roadmap