Explorer
Data Structures & Algorithms

Find all elements that appear more than n/3 times in an array.

Problem Statement

Given an integer array of size `n`, find all elements that appear more than `āŒŠ n/3 āŒ‹` times. Return the elements sorted in ascending order.

Examples

Input: nums = [3, 2, 3]

Output: [3]

Explanation: Combining the input according to Majority Element-II logic yields [3].

Input: nums = [1]

Output: [1]

Explanation: Combining the input according to Majority Element-II logic yields [1].

Input: nums = [1, 2]

Output: [1, 2]

Explanation: Combining the input according to Majority Element-II logic yields [1, 2].

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: At most two elements can appear strictly more than floor(n / 3) times. šŸ’” Hint 2: Extend Boyer-Moore Voting to maintain two candidates and two counters. šŸ’” Hint 3: A second verification pass is required to confirm that the selected candidates actually exceed the n/3 threshold.

Editorial & Approach

Problem Overview & Intuition

There can be at most 2 elements appearing strictly more than n/3 times. Using extended Boyer-Moore voting with two candidates and counters, we cancel triplets of distinct elements. A second verification pass confirms which candidates meet the threshold.

Step-by-Step Approach

  1. Initialize cand1 = null, cand2 = null, count1 = 0, count2 = 0.
  2. Pass 1: Find the top two potential candidates.
  3. Pass 2: Count actual frequencies of cand1 and cand2 in nums.
  4. If count > floor(n / 3), include in result.
  5. Return result sorted.

Optimal Implementation (JavaScript)

function majorityElementTwo(nums) {
  let cand1 = null, cand2 = null, count1 = 0, count2 = 0;
  for (let num of nums) {
    if (num === cand1) count1++;
    else if (num === cand2) count2++;
    else if (count1 === 0) { cand1 = num; count1 = 1; }
    else if (count2 === 0) { cand2 = num; count2 = 1; }
    else { count1--; count2--; }
  }
  const result = [];
  const threshold = Math.floor(nums.length / 3);
  let c1 = 0, c2 = 0;
  for (let num of nums) {
    if (num === cand1) c1++;
    else if (num === cand2) c2++;
  }
  if (c1 > threshold) result.push(cand1);
  if (c2 > threshold) result.push(cand2);
  return result.sort((a, b) => a - b);
}

Complexity Analysis

Time Complexity O(N) ā€” two linear passes.
Space Complexity O(1) ā€” constant extra space.

Edge Cases & Corner Traps Handled

  • Only 1 majority element exists.
  • 2 majority elements exist.
  • No element occurs > n/3 times: returns [].

Majority Element-II

Hard
Given an integer array of size `n`, find all elements that appear more than `āŒŠ n/3 āŒ‹` times. Return the elements sorted in ascending order.
Example Scenarios
1Example 1
Input: nums = [3, 2, 3]
Output: [3]
Explanation:

Combining the input according to Majority Element-II logic yields [3].

2Example 2
Input: nums = [1]
Output: [1]
Explanation:

Combining the input according to Majority Element-II logic yields [1].

3Example 3
Input: nums = [1, 2]
Output: [1, 2]
Explanation:

Combining the input according to Majority Element-II logic yields [1, 2].

Editor
Loading Editor...
nums =
[3, 2, 3]
Output:Click "Run" above to execute and verify your code here.
[3]