Majority Element II

Medium· voting· counting

Problem

Find every value that appears more than n / 3 times in an array of length n. There can be at most two such values. Aim for linear time and constant space.

Examples

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

Output: [1,2]

Both 1 and 2 appear 3 times, which exceeds 7 / 3.

Input: nums = [5]

Output: [5]

Constraints

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

Hints & approach

Hint 1

Why can there be at most two answers?

Hint 2

Extend the voting idea from the n / 2 version to track two candidates at once.

Hint 3

Candidates from voting are only possibilities; confirm them with a second counting pass.

Approachtry the hints first

Run an extended Boyer-Moore vote with two candidates and two counters. A value matching a candidate bumps that counter; otherwise it fills an empty slot, or if both slots are busy it decrements both counters (cancelling a triple of distinct values). Any value above n / 3 survives this cancellation as a candidate. A second pass counts the two candidates and keeps only those that really exceed n / 3.

Time O(n) · Space O(1)

← PreviousNext Permutation Next →Rearrange Array Elements by Sign