Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Majority Element II

MEDIUMProblemSolveExternal Links

Description

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

Return a list of all such majority elements. The result can be returned in any order.

A key mathematical observation is that there can be at most two elements in any array that appear more than ⌊n/3⌋ times. This is because if three or more elements each appeared more than n/3 times, their combined count would exceed n, which is impossible since the array only has n elements.

Examples

Example 1

Input: nums = [3, 2, 3]

Output: [3]

Explanation: The array has 3 elements, so ⌊3/3⌋ = 1. We need elements appearing more than 1 time. The element 3 appears twice (at indices 0 and 2), while 2 appears only once. Since 2 > 1, element 3 qualifies as a majority element.

Example 2

Input: nums = [1]

Output: [1]

Explanation: The array has 1 element, so ⌊1/3⌋ = 0. We need elements appearing more than 0 times. The element 1 appears once, which is greater than 0, so it is a majority element.

Example 3

Input: nums = [1, 2]

Output: [1, 2]

Explanation: The array has 2 elements, so ⌊2/3⌋ = 0. Both elements appear once, which is greater than 0, so both qualify as majority elements.

Constraints

  • 1 ≤ nums.length ≤ 5 × 10^4
  • -10^9 ≤ nums[i] ≤ 10^9

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to count how many times each element appears in the array and check whether that count exceeds the threshold ⌊n/3⌋.

Imagine you are a teacher collecting votes from a class. You pick each unique student name from a hat, then manually count how many times that name appears on all the ballots. If any name appears on more than a third of the ballots, you write it down as a winner.

For every element in the array, we scan the entire array to count its occurrences. If the count is greater than ⌊n/3⌋ and we have not already added it to our result, we include it.

Step-by-Step Explanation

Let's trace through with nums = [3, 2, 3], threshold = ⌊3/3⌋ = 1:

Step 1: Start with i = 0, element nums[0] = 3. We need to count how many times 3 appears in the entire array.

Step 2: Scan the array to count occurrences of 3:

  • nums[0] = 3 → match, count = 1
  • nums[1] = 2 → no match, count = 1
  • nums[2] = 3 → match, count = 2
  • Final count of 3 = 2

Step 3: Is count(3) = 2 > threshold 1? YES. Add 3 to result. Result = [3].

Step 4: Move to i = 1, element nums[1] = 2. Count occurrences of 2:

  • nums[0] = 3 → no match, count = 0
  • nums[1] = 2 → match, count = 1
  • nums[2] = 3 → no match, count = 1
  • Final count of 2 = 1

Step 5: Is count(2) = 1 > threshold 1? NO (1 is not greater than 1). Do not add 2.

Step 6: Move to i = 2, element nums[2] = 3. We already processed 3, so skip.

Result: [3]

Brute Force — Counting Each Element's Frequency — For each element, we scan the entire array to count its occurrences and compare against the threshold ⌊n/3⌋.

Algorithm

  1. Calculate the threshold: threshold = ⌊n/3⌋
  2. Initialize an empty result list
  3. For each element nums[i] in the array:
    a. If nums[i] is already in the result, skip it
    b. Count the occurrences of nums[i] by scanning the entire array
    c. If the count is greater than threshold, add nums[i] to the result
  4. Return the result list

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        int threshold = n / 3;
        vector<int> result;
        
        for (int i = 0; i < n; i++) {
            // Check if nums[i] is already in result
            bool alreadyAdded = false;
            for (int r : result) {
                if (r == nums[i]) {
                    alreadyAdded = true;
                    break;
                }
            }
            if (alreadyAdded) continue;
            
            // Count occurrences of nums[i]
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            
            if (count > threshold) {
                result.push_back(nums[i]);
            }
        }
        
        return result;
    }
};
class Solution:
    def majorityElement(self, nums: list[int]) -> list[int]:
        n = len(nums)
        threshold = n // 3
        result = []
        
        for i in range(n):
            # Skip if already in result
            if nums[i] in result:
                continue
            
            # Count occurrences of nums[i]
            count = 0
            for j in range(n):
                if nums[j] == nums[i]:
                    count += 1
            
            if count > threshold:
                result.append(nums[i])
        
        return result
import java.util.*;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length;
        int threshold = n / 3;
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            // Skip if already in result
            if (result.contains(nums[i])) continue;
            
            // Count occurrences of nums[i]
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            
            if (count > threshold) {
                result.add(nums[i]);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n elements, we perform a full scan of the array to count its occurrences, which takes O(n) time. In the worst case (all distinct elements), we do this for every element, giving n × n = O(n²) total operations.

Space Complexity: O(1)

The result list contains at most 2 elements (since at most 2 elements can appear more than ⌊n/3⌋ times). We use only a constant amount of extra variables. The output list does not count toward space complexity.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity. With n up to 5 × 10^4, that means up to 2.5 × 10^9 operations — far too slow for typical time limits of 1-2 seconds.

The core inefficiency is that we recount elements repeatedly. If the array is [1, 1, 1, 2, 2, 2, 3, 3, 3], we count the frequency of 1 three separate times (once for each occurrence of 1), doing redundant work.

What if we could count the frequency of every element in a single pass? A hash map lets us do exactly that — store each element's count as we encounter it, then filter for elements exceeding the threshold.

Better Approach - Hash Map Counting

Intuition

Instead of recounting each element from scratch, we can tally every element's frequency in a single pass through the array using a hash map. Think of it like sorting ballots into labeled piles: as each ballot comes in, you place it on the correct pile. At the end, you simply check which piles are tall enough (more than n/3 ballots).

We iterate through the array once, incrementing a counter in the hash map for each element. Then we iterate through the hash map entries and collect any element whose count exceeds ⌊n/3⌋.

Step-by-Step Explanation

Let's trace through with nums = [3, 2, 3], threshold = ⌊3/3⌋ = 1:

Step 1: Initialize an empty hash map: freq = {}.

Step 2: Process nums[0] = 3.

  • 3 is not in the map. Add it: freq = {3: 1}.

Step 3: Process nums[1] = 2.

  • 2 is not in the map. Add it: freq = {3: 1, 2: 1}.

Step 4: Process nums[2] = 3.

  • 3 is already in the map. Increment: freq = {3: 2, 2: 1}.

Step 5: Frequency counting complete. Now scan the map for entries with count > 1.

Step 6: Check entry (3, 2): Is 2 > 1? YES. Add 3 to result.

Step 7: Check entry (2, 1): Is 1 > 1? NO. Skip.

Result: [3]

Hash Map Frequency Counting — Build a frequency map in one pass, then filter for elements appearing more than ⌊n/3⌋ times.

Algorithm

  1. Calculate the threshold: threshold = ⌊n/3⌋
  2. Create an empty hash map freq to store element → count
  3. For each element num in the array:
    • If num exists in freq, increment its count
    • Otherwise, set freq[num] = 1
  4. Initialize an empty result list
  5. For each (key, count) pair in freq:
    • If count > threshold, add key to result
  6. Return the result list

Code

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        int threshold = n / 3;
        unordered_map<int, int> freq;
        
        // Count frequency of each element
        for (int num : nums) {
            freq[num]++;
        }
        
        // Collect elements exceeding threshold
        vector<int> result;
        for (auto& [val, count] : freq) {
            if (count > threshold) {
                result.push_back(val);
            }
        }
        
        return result;
    }
};
class Solution:
    def majorityElement(self, nums: list[int]) -> list[int]:
        n = len(nums)
        threshold = n // 3
        freq = {}
        
        # Count frequency of each element
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        
        # Collect elements exceeding threshold
        result = []
        for val, count in freq.items():
            if count > threshold:
                result.append(val)
        
        return result
import java.util.*;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length;
        int threshold = n / 3;
        Map<Integer, Integer> freq = new HashMap<>();
        
        // Count frequency of each element
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        // Collect elements exceeding threshold
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getValue() > threshold) {
                result.add(entry.getKey());
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make a single pass through the array of n elements to build the frequency map — each insertion/update in the hash map takes O(1) on average. Then we iterate through the map entries (at most n unique entries) to filter. Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

In the worst case (all distinct elements), the hash map stores n key-value pairs. This additional space grows linearly with the input size.

Why This Approach Is Not Efficient

The hash map approach runs in O(n) time, which is already optimal in terms of time complexity. However, it uses O(n) extra space for the frequency map.

The problem's follow-up challenge asks: Can you solve it in O(n) time and O(1) space?

With up to 5 × 10^4 elements, the hash map could store tens of thousands of entries. While this is acceptable in practice, we can do better by leveraging a key mathematical insight: at most two elements can appear more than ⌊n/3⌋ times. This means we only need to track two candidates, not the frequency of every element.

The Boyer-Moore Voting Algorithm, extended for the n/3 threshold, achieves exactly this — O(n) time with O(1) space.

Optimal Approach - Boyer-Moore Voting Algorithm

Intuition

The Boyer-Moore Voting Algorithm is based on a clever "cancellation" strategy. The key insight is that at most two elements can appear more than ⌊n/3⌋ times in an array. So we only need to maintain two candidates with their running vote counts.

Think of it as a survival game with three-way battles. Imagine a crowd of people holding signs with numbers. Whenever three people hold three different numbers, all three leave the crowd simultaneously. After all such eliminations, whoever remains must be the strongest contenders — elements that appeared so frequently that even after losing votes to cancellations, they survived.

The algorithm works in two passes:

Pass 1 — Find candidates: We maintain two candidate slots, each with a value and a vote counter. As we process each element:

  • If it matches a candidate, that candidate gains a vote
  • If a candidate slot is empty (count is zero), the element claims that slot
  • If neither condition applies, both candidates lose a vote (the three-way cancellation)

Pass 2 — Verify candidates: The first pass gives us at most two potential majority elements, but they might be false positives. We count their actual occurrences to confirm they truly exceed the ⌊n/3⌋ threshold.

The reason verification is needed: the cancellation process guarantees that any true majority element will survive as a candidate, but non-majority elements can also survive if they happen to be the last ones standing after all cancellations.

Step-by-Step Explanation

Let's trace through with nums = [3, 2, 3, 1, 3, 2, 1, 1], n = 8, threshold = ⌊8/3⌋ = 2:

Pass 1 — Finding Candidates:

Step 1: Initialize candidates: cand1 = None (count1 = 0), cand2 = None (count2 = 0).

Step 2: Process nums[0] = 3. count1 is 0 → claim slot 1. Set cand1 = 3, count1 = 1.

Step 3: Process nums[1] = 2. Does not match cand1 (3). count2 is 0 → claim slot 2. Set cand2 = 2, count2 = 1.

Step 4: Process nums[2] = 3. Matches cand1 (3) → increment count1 to 2.

Step 5: Process nums[3] = 1. Does not match cand1 (3) or cand2 (2). Both counts > 0 → cancel: count1 = 1, count2 = 0.

Step 6: Process nums[4] = 3. Matches cand1 (3) → increment count1 to 2.

Step 7: Process nums[5] = 2. Does not match cand1 (3). count2 is 0 → claim slot 2. Set cand2 = 2, count2 = 1.

Step 8: Process nums[6] = 1. Does not match cand1 (3) or cand2 (2). Both counts > 0 → cancel: count1 = 1, count2 = 0.

Step 9: Process nums[7] = 1. Does not match cand1 (3). count2 is 0 → claim slot 2. Set cand2 = 1, count2 = 1.

After Pass 1: cand1 = 3 (count1 = 1), cand2 = 1 (count2 = 1).

Pass 2 — Verification:

Step 10: Count actual occurrences of candidate 3: appears at indices 0, 2, 4 → count = 3. Is 3 > 2? YES.

Step 11: Count actual occurrences of candidate 1: appears at indices 3, 6, 7 → count = 3. Is 3 > 2? YES.

Result: [3, 1]

Boyer-Moore Voting — Two-Candidate Survival Game — Watch how two candidate slots compete and survive through vote increments and three-way cancellations, followed by a verification pass.

Algorithm

Pass 1 — Candidate Selection:

  1. Initialize two candidate variables cand1, cand2 with distinct values and two counters count1 = 0, count2 = 0
  2. For each element num in the array:
    • If num == cand1, increment count1
    • Else if num == cand2, increment count2
    • Else if count1 == 0, set cand1 = num, count1 = 1
    • Else if count2 == 0, set cand2 = num, count2 = 1
    • Else, decrement both count1 and count2

Pass 2 — Verification:
3. Count actual occurrences of cand1 and cand2 in the array
4. Add each candidate to the result if its count exceeds ⌊n/3⌋
5. Return the result

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        
        // Pass 1: Find candidates using Boyer-Moore Voting
        int cand1 = 0, cand2 = 1;  // Initialize to different values
        int count1 = 0, count2 = 0;
        
        for (int num : 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--;
            }
        }
        
        // Pass 2: Verify candidates
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == cand1) count1++;
            else if (num == cand2) count2++;
        }
        
        int threshold = n / 3;
        vector<int> result;
        if (count1 > threshold) result.push_back(cand1);
        if (count2 > threshold) result.push_back(cand2);
        
        return result;
    }
};
class Solution:
    def majorityElement(self, nums: list[int]) -> list[int]:
        n = len(nums)
        
        # Pass 1: Find candidates using Boyer-Moore Voting
        cand1, cand2 = 0, 1  # Initialize to different values
        count1, count2 = 0, 0
        
        for num in nums:
            if num == cand1:
                count1 += 1
            elif num == cand2:
                count2 += 1
            elif count1 == 0:
                cand1 = num
                count1 = 1
            elif count2 == 0:
                cand2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1
        
        # Pass 2: Verify candidates
        count1 = 0
        count2 = 0
        for num in nums:
            if num == cand1:
                count1 += 1
            elif num == cand2:
                count2 += 1
        
        threshold = n // 3
        result = []
        if count1 > threshold:
            result.append(cand1)
        if count2 > threshold:
            result.append(cand2)
        
        return result
import java.util.*;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length;
        
        // Pass 1: Find candidates using Boyer-Moore Voting
        int cand1 = 0, cand2 = 1;  // Initialize to different values
        int count1 = 0, count2 = 0;
        
        for (int num : 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--;
            }
        }
        
        // Pass 2: Verify candidates
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == cand1) count1++;
            else if (num == cand2) count2++;
        }
        
        int threshold = n / 3;
        List<Integer> result = new ArrayList<>();
        if (count1 > threshold) result.add(cand1);
        if (count2 > threshold) result.add(cand2);
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make two linear passes through the array. The first pass identifies candidates in O(n) time — each element involves only constant-time comparisons and counter updates. The second pass counts occurrences of at most two candidates, also O(n). Total: O(n) + O(n) = O(n).

Space Complexity: O(1)

We use only a fixed number of variables: two candidate values, two counters, and a threshold. The result list contains at most 2 elements. No auxiliary data structures that grow with input size are used. This is a significant improvement over the hash map approach which required O(n) space.