DiffPush Tier Arrays · Hard O(n) · O(1)
A fraud review runs over a merged stream of account ids from several feeds and wants every account that shows up in more than one third of the records. At most two such accounts can exist, and the stream is far too large to tally with a table. Identify them in a single pass with constant extra memory.
Input: An array nums of n integers, one account id per record.
Output: All values occurring more than floor(n / 3) times, in any order; the result may be empty.
1 <= n <= 5 * 10^4-10^9 <= nums[i] <= 10^9Input: {"nums":[3,2,3]}
Output: [3]
Account 3 appears twice out of three records, clearing the one third threshold.
Input: {"nums":[1]}
Output: [1]
A single record already exceeds one third of one, so it qualifies.