Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Difficulty

medium

Companies

AmazonGoogle

Topic

Array / Hashingarray hash-table greedy

Examples

Input: [3,2,3]

Output: [3]

Input: [1,1,1,3,3,2,2,2]

Output: [1,2]

Hints

At most 2 elements can appear more than n/3 times

Use Boyer-Moore Voting Algorithm extension

First pass: find potential candidates, second pass: verify

Related Problems

majority-element

Majority Element II

Given an integer array of size `n`, find all elements that appear more than `⌊ n/3 ⌋` times.