Elements Appearing More Than n/3 Times

Problem Given an integer array of size n, find all elements that appear more than floor(n/3) times.

Input / Output

• Input: array nums of length n.
• Output: a list of every value occurring more than floor(n/3) times, in any order.

Constraints

• Array length up to 5 * 10^4.
• Target O(n) time and O(1) space — a hash map of counts is O(n) time but O(n) space, so it is the baseline to beat.
• The answer may be empty, hold one element, or hold two — never more.
• Values may be negative and arbitrarily large, ruling out a count array indexed by value.

Example

• [3,2,3] -> [3]
• [1,1,1,3,3,2,2,2] -> [1,2]
• [1,2,3] -> [] — nothing exceeds floor(3/3)=1; this case exposes an implementation that skips the verification pass, since voting always leaves two candidates behind.