Back to ArraysMajority Element II
Medium

Majority Element II

MediumOptionalBoyer-Moore Voting

Given an array, return all elements that appear more than ⌊n/3⌋ times.

Examples

Example 1

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

Explanation: 3 appears twice out of 3 elements, comfortably more than ⌊3/3⌋ = 1 time; 2 appears only once.

Example 2

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

Explanation: With n = 1, the single element trivially appears more than ⌊1/3⌋ = 0 times.

Example 3

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

Explanation: n = 2, so the threshold is more than ⌊2/3⌋ = 0 times — both elements qualify.

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

Follow-up

How would the voting step change if the threshold were more than n/4 instead of n/3?

Loading editor…

Code execution is coming soon.