Pattern visualizer
Majority Element II
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. Animated on: nums = [1, 2, 2, 3, 2, 1, 1] — return every value appearing more than floor(n/3) times..
Boyer-Moore with two seats — cancellation in threes
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.
1FUNCTION majorityElementII(nums)2 c1 <- NONE3 c2 <- NONE4 k1 <- 05 k2 <- 06 FOR i <- 0 TO LENGTH(nums) - 17 IF nums[i] = c1 THEN k1 <- k1 + 18 ELSE IF nums[i] = c2 THEN k2 <- k2 + 19 ELSE IF k1 = 0 THEN c1 <- nums[i], k1 <- 110 ELSE IF k2 = 0 THEN c2 <- nums[i], k2 <- 111 ELSE k1 <- k1 - 1, k2 <- k2 - 112 RETURN EACH c IN c1, c2 WITH COUNT(nums, c) > LENGTH(nums) / 3
← / → step · space play · Home restart