229. Majority Element II

Medium

Array

Hash Table

Sorting

Counting

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

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

Follow up: Could you solve the problem in linear time and in O(1) space?

Hint 1

Think about the possible number of elements that can appear more than ⌊ n/3 ⌋ times in the array.

Hint 2

It can be at most two. Why?

Hint 3

Consider using Boyer-Moore Voting Algorithm, which is efficient for finding elements that appear more than a certain threshold.

Acceptance

55.6%

Submissions

2,105,085

Accepted

1,169,722