Majority Element II

1. Define the problem

Given an integer array of size n, return all elements that appear more than n / 3 times . There can be at most two such elements, since a third value appearing more than a third of the time would leave no room for the others. Use the Boyer-Moore voting trick extended to track two candidates at once: each candidate survives by canceling out one occurrence of anything that is neither of the two current candidates, then a second pass confirms which candidates really do appear often enough.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
-10⁹ ≤ nums_i ≤ 10⁹

Example

Inputnums = [1, 1, 1, 3, 3, 2, 2, 2]

Output[1, 2]

Explanation n = 8, so anything appearing more than 8/3 ≈ 2.67 times qualifies. 1 appears 3 times, 2 appears 3 times, and 3 appears only 2 times, so the answer is [1, 2] (order does not matter).

2. Know the words first

In plain terms

Boyer-Moore voting trick: Tracking a running "candidate" and a counter: matching values increase the counter, mismatches decrease it, and hitting zero means the candidate gets replaced.

3. Visualize the solution

Track two candidates, then confirm with a second pass

Statuscandidate1

The first three values are all 1: candidate1 locks onto 1 and its counter climbs to 3.

What happens in this step

values 1, 1, 1
candidate1 = 1, count1 = 3
candidate2 = null, count2 = 0

Step 1 of 6

Steps to visualize

Walk the array once, keeping two candidate values and their counters.
A value matching an existing candidate bumps that counter; otherwise, if a counter is at zero, that value takes over as the new candidate.
If neither counter is at zero and the value matches neither candidate, both counters get decremented instead.
Once the walk finishes, count how many times each surviving candidate actually appears in the whole array.
Only candidates whose true count exceeds n / 3 make it into the final answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track two candidates, then confirm with a second pass

Statuscandidate1

The first three values are all 1: candidate1 locks onto 1 and its counter climbs to 3.

What happens in this step

values 1, 1, 1
candidate1 = 1, count1 = 3
candidate2 = null, count2 = 0

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function majorityElement(nums) {
  let candidate1 = null;
  let candidate2 = null;
  let count1 = 0;
  let count2 = 0;

  for (const num of nums) {
    if (candidate1 === num) {
      count1++;
    } else if (candidate2 === num) {
      count2++;
    } else if (count1 === 0) {
      candidate1 = num;
      count1 = 1;
    } else if (count2 === 0) {
      candidate2 = num;
      count2 = 1;
    } else {
      count1--;
      count2--;
    }
  }

  count1 = 0;
  count2 = 0;

  for (const num of nums) {
    if (num === candidate1) {
      count1++;
    } else if (num === candidate2) {
      count2++;
    }
  }

  const result = [];
  const threshold = Math.floor(nums.length / 3);

  if (count1 > threshold) {
    result.push(candidate1);
  }
  if (count2 > threshold) {
    result.push(candidate2);
  }

  return result;
}

Time: O(n)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 1, 1, 3, 3, 2, 2, 2]`	`[1, 2]`	example from the docstring
`nums = [3, 2, 3]`	`[3]`	smallest classic example, a single majority value
`nums = [2, 2, 2, 2]`	`[2]`	every value the same, comfortably over the threshold
`nums = [1, 2, 3, 4]`	`[]`	every value appears exactly once, none crossing the threshold
`nums = [1, 2]`	`[1, 2]`	both values qualify when the threshold is small enough
`nums = [2, 2, 1, 3]`	`[2]`	only one of the surviving candidates actually clears the threshold

Majority Element II