Log inSign up
mediumLeetCodeNot Started

Majority Element II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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

---

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

---

### Follow-up: - Could you solve the problem in linear time O(n) and in O(1) auxiliary space?

Example 1 · Example 1 (Single Majority Candidate):

Input: nums = [3, 2, 3]
Output: [3]
Explanation: The array size is 3. ⌊3 / 3⌋ = 1. Element 3 appears 2 times (> 1), so it is the only majority element.

Example 2 · Example 2 (Two Majority Candidates):

Input: nums = [1, 2]
Output: [1, 2]
Explanation: The array size is 2. ⌊2 / 3⌋ = 0. Both 1 and 2 appear 1 time (> 0), so both are returned.

Example 3 · Example 3 (Tied Frequency Under Threshold):

Input: nums = [1, 2, 3, 4]
Output: []
Explanation: The array size is 4. ⌊4 / 3⌋ = 1. Every element appears only 1 time, which is not strictly greater than 1.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array Indexing
  • Basic Time & Space Complexity Analysis

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove why at most (k - 1) majority elements can exist for threshold > n / k.
  • Master the multi-candidate Boyer-Moore elimination algorithm.
  • Understand why a verification pass is mandatory for threshold > n / 3.
  • Implement clean, standalone solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding majority elements exceeding threshold n / k.
  • Strict O(1) auxiliary space constraint.
  • Frequency threshold based on integer division (n/2, n/3, n/k).

Algorithmic Decision Tree:

  • For threshold > n / 2: Single-candidate Boyer-Moore (1 candidate, 1 counter).
  • For threshold > n / 3: Dual-candidate Boyer-Moore (2 candidates, 2 counters).
  • For threshold > n / k: General Boyer-Moore with (k - 1) candidates and counters.

Connected Patterns:

Majority Element (n/2): Single candidate Boyer-Moore.Check if Number Is Majority Element in Sorted Array: Binary search range count.

1. Nested Loops Counting

Intuition

For every unique element, count its occurrences across the entire array using a nested loop and check if count > floor(n / 3).

Algorithm

  1. 1. Let n = nums.length, threshold = floor(n / 3).
  2. 2. Initialize result list.
  3. 3. For i from 0 to n-1: - If nums[i] already in result, continue. - Count occurrences of nums[i] across nums. - If count > threshold, append nums[i] to result.
  4. 4. Return result.

Brute Force All-Elements Frequency Scan

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [1, 1, 1, 3, 3, 2, 2, 2]
Current operationSTEP 1 OF 8
Phase 1 — Step 1: Step 1: Target element is nums[0] = 1
Visual state
Values and pointers at this exact step
array
S
1
1
1
3
3
2
2
2
0
↑ i=0 (Test 1)
1
2
3
4
5
6
7
Variables at this step
Threshold
2
Candidate
1
Count
0
Result
[]
Check / comparison
Threshold = floor(n/3) = floor(8/3) = 2. Must appear >= 3 times.
Decision / next transition
Initialize count = 0. Inner loop j will scan all 8 elements.
Why this step matters

Phase 1 — Step 1: Step 1: Target element is nums[0] = 1. To be a majority element, count must be > 8/3 = 2 (i.e. at least 3 occurrences).

Step 1 / 8
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> majorityElement(int[] nums) {
6 List<Integer> res = new ArrayList<>();
7 int n = nums.length;
8 int threshold = n / 3;
9
10 for (int i = 0; i < n; i++) {
11 if (res.contains(nums[i])) continue;
12 int count = 0;
13 for (int j = 0; j < n; j++) {
14 if (nums[j] == nums[i]) count++;
15 }
16 if (count > threshold) res.add(nums[i]);
17 }
18 return res;
19 }
20 }
21
22 public static void main(String[] args) {
23 Solution sol = new Solution();
24 int[] nums = {1, 1, 1, 3, 3, 2, 2, 2};
25 System.out.println("Majority elements (> n/3): " + sol.majorityElement(nums));
26 }
27}

Time & Space Complexity

  • Time complexity: O(N^2) — Nested loops examine all N elements against the entire array of size N, resulting in O(N2) time.
  • Space complexity: O(1) — Auxiliary space is O(1) as at most 2 elements can satisfy the condition.

Why Brute Force Doesn't Scale:

Since at most 2 elements can satisfy the > n/3 condition, we only need to track 2 candidate integers and their balance counters. When we see 3 mutually distinct elements, canceling all 3 reduces array size without altering the relative majority of the surviving elements. This brings auxiliary space down from O(N) to O(1).

For N = 50,000 unique ints: Hash map takes ~2 MB heap. Boyer-Moore uses 4 integer registers (16 bytes).

2. Hash Map Frequency Counting

Intuition

Use a Hash Map to record frequencies of all elements in a single pass, then filter elements with frequency > floor(n / 3).

Algorithm

  1. 1. Initialize Hash Map freqMap.
  2. 2. For each num in nums: freqMap[num] = freqMap.getOrDefault(num, 0) + 1.
  3. 3. For each [num, count] in freqMap: if count > n / 3, add num to result.
  4. 4. Return result.

Hash Map Frequency Counting Pass

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [1, 1, 1, 3, 3, 2, 2, 2]
Current operationSTEP 1 OF 8
Phase 1 — map = { 1: 1 }: Step 1: Initialize frequency map {}
Visual state
Values and pointers at this exact step
array
S
1
1
1
3
3
2
2
2
0
↑ i=0 (val 1)
1
2
3
4
5
6
7
Variables at this step
Map
{ 1: 1 }
Current
1
Check / comparison
Read nums[0] = 1. Insert into hash map with count 1.
Decision / next transition
map = { 1: 1 }
Why this step matters

Phase 1 — map = { 1: 1 }: Step 1: Initialize frequency map {}. Tally first element: map[1] = 1.

Step 1 / 8
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> majorityElement(int[] nums) {
6 List<Integer> res = new ArrayList<>();
7 Map<Integer, Integer> map = new HashMap<>();
8 int n = nums.length;
9
10 for (int num : nums) {
11 map.put(num, map.getOrDefault(num, 0) + 1);
12 }
13
14 for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
15 if (entry.getValue() > n / 3) {
16 res.add(entry.getKey());
17 }
18 }
19 return res;
20 }
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 int[] nums = {1, 1, 1, 3, 3, 2, 2, 2};
26 System.out.println("Majority elements (> n/3): " + sol.majorityElement(nums));
27 }
28}

Time & Space Complexity

  • Time complexity: O(N) — One pass to populate the hash map and one pass over at most N keys. Total time is O(N).
  • Space complexity: O(N) — Hash Map stores up to N distinct elements in the worst case, taking O(N) space.

3. Extended Boyer-Moore Voting Algorithm (2 Candidates)

Intuition

Maintain at most 2 candidates and 2 counters in O(1) space, followed by a second verification pass.

Algorithm

  1. 1. Initialize cand1 = 0, cand2 = 0, c1 = 0, c2 = 0.
  2. 2. Pass 1: - If num == cand1: c1++ - Else if num == cand2: c2++ - Else if c1 == 0: cand1 = num, c1 = 1 - Else if c2 == 0: cand2 = num, c2 = 1 - Else: c1--, c2--.
  3. 3. Pass 2: Count occurrences of cand1 and cand2 across nums.
  4. 4. Append cand1 if count(cand1) > n/3; append cand2 if count(cand2) > n/3 and cand2 != cand1.
  5. 5. Returns in O(N) time and O(1) space.

Extended Boyer-Moore 2-Candidate Voting Algorithm

2 of 2 questions left today
Step 1 / 10
Trace timeline10% explored
InputINPUT nums = [1, 1, 1, 3, 3, 2, 2, 2]
Current operationSTEP 1 OF 10
Phase 1 — cand1 = 1, c1 = 1, cand2 = null, c2 = 0: Step 1 (Idx 0): Counter 1 is zero
Visual state
Values and pointers at this exact step
array
S
1
1
1
3
3
2
2
2
0
↑ i=0 (val 1)
1
2
3
4
5
6
7
Variables at this step
cand1
1
c1
1
cand2
null
c2
0
Check / comparison
c1 == 0. Pick cand1 = nums[0] (1). c1 = 1.
Decision / next transition
cand1 = 1, c1 = 1, cand2 = null, c2 = 0.
Why this step matters

Phase 1 — cand1 = 1, c1 = 1, cand2 = null, c2 = 0: Step 1 (Idx 0): Counter 1 is zero. Assign cand1 = 1 and initialize c1 = 1.

Step 1 / 10
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> majorityElement(int[] nums) {
6 int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
7
8 for (int num : nums) {
9 if (num == candidate1) {
10 count1++;
11 } else if (num == candidate2) {
12 count2++;
13 } else if (count1 == 0) {
14 candidate1 = num;
15 count1 = 1;
16 } else if (count2 == 0) {
17 candidate2 = num;
18 count2 = 1;
19 } else {
20 count1--;
21 count2--;
22 }
23 }
24
25 // Verification pass
26 count1 = 0;
27 count2 = 0;
28 for (int num : nums) {
29 if (num == candidate1) count1++;
30 else if (num == candidate2) count2++;
31 }
32
33 List<Integer> res = new ArrayList<>();
34 int n = nums.length;
35 if (count1 > n / 3) res.add(candidate1);
36 if (count2 > n / 3) res.add(candidate2);
37 return res;
38 }
39 }
40
41 public static void main(String[] args) {
42 Solution sol = new Solution();
43 int[] nums = {1, 1, 1, 3, 3, 2, 2, 2};
44 System.out.println("Majority elements (> n/3): " + sol.majorityElement(nums));
45 }
46}

Time & Space Complexity

  • Time complexity: O(N) — Two linear passes of length N. Total time is O(2N) = O(N).
  • Space complexity: O(1) — Only uses candidate and counter variables. Auxiliary space is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Nested Loops CountingO(N^2)O(1)For every unique element, count its occurrences across the entire array using a nested loop and check if count > floor(n / 3).Redundant re-computation across iterations.
2.Approach 2: Hash Map Frequency CountingO(N)O(N)Use a Hash Map to record frequencies of all elements in a single pass, then filter elements with frequency > floor(n / 3).Redundant re-computation across iterations.
3.Approach 3: Extended Boyer-Moore Voting Algorithm (2 Candidates)OptimalO(N)O(1)Maintain at most 2 candidates and 2 counters in O(1) space, followed by a second verification pass.None. Optimal single pass.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • No elements exceed n / 3: Verification pass safely returns empty list [].
  • Array with only 1 element: Element trivially satisfies 1 > 0, returns [nums[0]].
  • All elements identical: Returns single unique candidate without duplicate entries in output.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the Pigeonhole Principle: 3 * (⌊n/3⌋ + 1) >= n + 1 > n, proving at most 2 elements can qualify.
  2. Emphasize the order of if-else conditions in Pass 1 to avoid assigning the same number to both candidates.
  3. Highlight why Pass 2 is strictly required, unlike standard Majority Element (n/2) where existence is guaranteed.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for undefined?

2.Why is the brute force approach suboptimal for large inputs in undefined?

3.Which data structure or technique enables the optimal solution for undefined?

Back to DSA Sheet