LeetCode 229 - Majority Element II

LeetCode Problem 229

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting, Counting

Solution

Problem Understanding

The problem asks us to find every element in an integer array that appears more than ⌊ n/3 ⌋ times, where n is the length of the array. The floor notation means we round down to the nearest integer. For example, if the array length is 8, then ⌊ 8/3 ⌋ = 2, so we are looking for elements that appear more than 2 times.

The input is an array of integers named nums. The output should be a list containing all values whose frequency exceeds the threshold n/3. The order of the returned elements does not matter.

An important observation is that there can be at most two such elements. This follows from simple counting logic. If there were three different elements each appearing more than n/3 times, their combined count would exceed n, which is impossible.

The constraints tell us several important things:

• The array can contain up to 5 * 10^4 elements, so inefficient quadratic solutions may become too slow.
• Values can range from -10^9 to 10^9, which means we cannot rely on counting arrays indexed by value.
• The follow-up explicitly asks for linear time and constant extra space, which strongly suggests that a specialized counting technique is expected.

Several edge cases are important:

• Arrays of length 1 or 2, where every element may qualify.
• Arrays with no repeated majority element.
• Arrays where exactly two elements exceed n/3.
• Arrays where candidate values change multiple times during processing.
• Negative integers and mixed values.

The problem guarantees that the input array is non-empty, so we never need to handle an empty input.

Approaches

Brute Force Approach

The most direct solution is to count the frequency of every number in the array. One naive method is to iterate through each element and count how many times it appears by scanning the entire array again.

For every number:

• Traverse the array
• Count occurrences
• If the count exceeds n/3, add it to the result if it is not already present

This works because it explicitly computes exact frequencies. However, the time complexity becomes O(n^2) since each element may trigger another full traversal of the array.

A slightly improved brute-force solution uses a hash map to store frequencies. This reduces the time complexity to O(n) but requires O(n) extra space. Although acceptable for the basic problem, it does not satisfy the follow-up requirement of constant extra space.

Key Insight for the Optimal Solution

The crucial insight is that there can be at most two elements appearing more than n/3 times.

This allows us to adapt the Boyer-Moore Voting Algorithm. The original Boyer-Moore algorithm finds a majority element appearing more than n/2 times using one candidate and one counter. Since this problem allows up to two majority elements, we maintain:

• Two candidate values
• Two counters

The algorithm works by canceling out different elements against each other. Whenever we encounter a new value that does not match either candidate and both counters are non-zero, we decrement both counters. This effectively removes one occurrence of three distinct elements from consideration.

If an element truly appears more than n/3 times, it cannot be completely eliminated through this cancellation process, so it will survive as one of the final candidates.

After the first pass, the candidates are only potential answers. We must perform a second pass to verify their actual frequencies.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Count each element by scanning the array repeatedly
Optimal	O(n)	O(1)	Boyer-Moore Voting Algorithm with two candidates

Algorithm Walkthrough

1. Initialize two candidate variables and two counters.

Since there can be at most two valid majority elements, we track two possible candidates. Initially, both counters are zero, meaning no candidates have been chosen yet. 2. Traverse the array once to determine potential candidates.

For each number in the array:

• If the number matches the first candidate, increment the first counter.
• Else if it matches the second candidate, increment the second counter.
• Else if the first counter is zero, replace the first candidate with the current number and set its counter to one.
• Else if the second counter is zero, replace the second candidate with the current number and set its counter to one.
• Otherwise, decrement both counters.

The decrement step is the core of the cancellation process. It removes influence from groups of three distinct values. 3. Verify the candidates.

After the first traversal, the candidates are only possible answers. We count how many times each candidate actually appears in the array. 4. Build the result list.

Add any candidate whose frequency exceeds n/3 to the result.

Why it works

The algorithm relies on the fact that removing three distinct elements from the array cannot eliminate a true majority element occurring more than n/3 times. Since any valid majority element appears too frequently to be completely canceled out, it must remain as one of the final candidates after the cancellation process. The second pass guarantees correctness by verifying actual frequencies.

Python Solution

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        candidate1 = None
        candidate2 = None
        count1 = 0
        count2 = 0

        # First pass: find potential candidates
        for num in nums:
            if candidate1 == num:
                count1 += 1
            elif candidate2 == num:
                count2 += 1
            elif count1 == 0:
                candidate1 = num
                count1 = 1
            elif count2 == 0:
                candidate2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1

        # Second pass: verify frequencies
        count1 = 0
        count2 = 0

        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1

        result = []
        threshold = len(nums) // 3

        if count1 > threshold:
            result.append(candidate1)

        if count2 > threshold:
            result.append(candidate2)

        return result

The implementation follows the Boyer-Moore majority voting strategy closely.

The first section initializes two candidate variables and their counters. The candidates start as None because no values have been selected yet.

The first loop performs the candidate selection phase. Matching candidates increase their counters, empty candidate slots are filled when counters reach zero, and conflicting values reduce both counters simultaneously.

The second phase resets the counters and performs verification. This is necessary because the first pass only identifies possible majority elements, not guaranteed ones.

Finally, the result list is constructed by checking whether each verified candidate exceeds the required threshold.

Go Solution

func majorityElement(nums []int) []int {
    var candidate1, candidate2 int
    count1, count2 := 0, 0

    // First pass: find potential candidates
    for _, num := range 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--
        }
    }

    // Second pass: verify frequencies
    count1, count2 = 0, 0

    for _, num := range nums {
        if num == candidate1 {
            count1++
        } else if num == candidate2 {
            count2++
        }
    }

    result := []int{}
    threshold := len(nums) / 3

    if count1 > threshold {
        result = append(result, candidate1)
    }

    if count2 > threshold {
        result = append(result, candidate2)
    }

    return result
}

The Go implementation mirrors the Python logic closely. Since Go does not support None, the candidate variables are initialized to zero values, but this is safe because the counters determine whether a candidate slot is active.

Slices are used for the result list, and integer division naturally performs floor division in Go, which matches the problem requirement.

Worked Examples

Example 1

Input:

nums = [3,2,3]

Threshold:

⌊3/3⌋ = 1

We need elements appearing more than once.

Step	Current Number	candidate1	count1	candidate2	count2
Start	-	None	0	None	0
1	3	3	1	None	0
2	2	3	1	2	1
3	3	3	2	2	1

Verification step:

• 3 appears 2 times
• 2 appears 1 time

Result:

[3]

Example 2

Input:

nums = [1]

Threshold:

⌊1/3⌋ = 0

Any element appearing more than zero times qualifies.

Step	Current Number	candidate1	count1	candidate2	count2
Start	-	None	0	None	0
1	1	1	1	None	0

Verification:

• 1 appears once

Result:

[1]

Example 3

Input:

nums = [1,2]

Threshold:

⌊2/3⌋ = 0

Both elements qualify.

Step	Current Number	candidate1	count1	candidate2	count2
Start	-	None	0	None	0
1	1	1	1	None	0
2	2	1	1	2	1

Verification:

• 1 appears once
• 2 appears once

Result:

[1,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Two linear passes through the array
Space	O(1)	Only a fixed number of variables are used

The algorithm performs two complete traversals of the array. The first determines the candidate majority elements, and the second verifies their frequencies. Since both traversals are linear, the overall time complexity is O(n).

The space complexity remains constant because we only store two candidates, two counters, and a small result list. No auxiliary data structures proportional to input size are used.

Test Cases

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        candidate1 = None
        candidate2 = None
        count1 = 0
        count2 = 0

        for num in nums:
            if candidate1 == num:
                count1 += 1
            elif candidate2 == num:
                count2 += 1
            elif count1 == 0:
                candidate1 = num
                count1 = 1
            elif count2 == 0:
                candidate2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1

        count1 = 0
        count2 = 0

        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1

        result = []
        threshold = len(nums) // 3

        if count1 > threshold:
            result.append(candidate1)

        if count2 > threshold:
            result.append(candidate2)

        return result

solution = Solution()

assert solution.majorityElement([3, 2, 3]) == [3]  # Basic majority case
assert solution.majorityElement([1]) == [1]  # Single element
assert sorted(solution.majorityElement([1, 2])) == [1, 2]  # Two valid answers
assert solution.majorityElement([2, 2, 1, 3]) == [2]  # One clear majority
assert sorted(solution.majorityElement([1, 1, 1, 2, 2, 2, 3])) == [1, 2]  # Two majority elements
assert solution.majorityElement([1, 2, 3, 4]) == []  # No majority elements
assert solution.majorityElement([-1, -1, -1, 2, 3]) == [-1]  # Negative numbers
assert solution.majorityElement([0, 0, 0]) == [0]  # All identical elements
assert sorted(solution.majorityElement([4, 4, 4, 5, 5, 5, 6])) == [4, 5]  # Two large groups
assert solution.majorityElement([1, 2, 3, 1, 2, 1, 1]) == [1]  # Candidate switching stress case

Test	Why
[3,2,3]	Standard example with one majority
[1]	Smallest valid input
[1,2]	Both elements qualify
[2,2,1,3]	Single majority with distractions
[1,1,1,2,2,2,3]	Exactly two valid majority elements
[1,2,3,4]	No element exceeds threshold
[-1,-1,-1,2,3]	Handles negative integers
[0,0,0]	All values identical
[4,4,4,5,5,5,6]	Two balanced majority groups
[1,2,3,1,2,1,1]	Frequent candidate replacement

Edge Cases

One important edge case is very small arrays. When the array length is 1 or 2, the threshold ⌊ n/3 ⌋ becomes zero. That means every distinct element qualifies. A buggy implementation might incorrectly assume only one answer exists or mishandle candidate initialization. The algorithm handles this naturally because the verification step checks frequencies against the computed threshold.

Another important case is when no element appears more than n/3 times. For example, [1,2,3,4] has no valid answer. The candidate selection phase will still produce some candidates because it must maintain two possible values, but the second verification pass prevents incorrect results from being returned.

A third tricky case occurs when candidates change repeatedly during traversal. Arrays such as [1,2,3,1,2,1,1] cause multiple decrement operations and candidate replacements. An incorrect implementation may lose track of the true majority element during cancellation. The Boyer-Moore logic guarantees that true majority elements survive the elimination process, and the verification pass confirms the final answer accurately.