The symbol that dominates the tape

Question

One symbol traded so heavily today that it accounts for strictly more than half of all prints on the tape. Find it using only constant extra memory (a hash-count table would work but is not allowed here).

tape = ["A", "B", "A", "A", "C", "A", "A"]
-> "A"          # A is 5 of 7 prints

Return the majority symbol, assuming one exists. Aim for $O(n)$ time and $O(1)$ space.

Accepted Answer

Boyer-Moore voting keeps a single candidate and a counter. Each element that matches the candidate is a vote for it; each mismatch is a vote against. When the counter reaches zero the candidate is "defeated" and the next element becomes the new candidate. Because the true majority occurs more than n / 2 times, its votes cannot all be cancelled, so it survives as the final candidate. Tracing ["A", "B", "A", "A", "C", "A", "A"]: the counter dips when B and C appear but never hits zero on a wrong symbol long enough to unseat A, which ends as the candidate. Time O(n), space O(1). The algorithm as…

The symbol that dominates the tape

Your answer

More Coding questions