229. Majority Element II - Explanation

Description

You are given an integer array nums of size n, find all elements that appear more than ⌊ n/3 ⌋ times. You can return the result in any order.

Example 1:

Input: nums = [5,2,3,2,2,2,2,5,5,5]

Output: [2,5]

Example 2:

Input: nums = [4,4,4,4,4]

Output: [4]

Example 3:

Input: nums = [1,2,3]

Output: []

Constraints:

1 <= nums.length <= 50,000.
-1,000,000,000 <= nums[i] <= 1,000,000,000

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

Elements appearing more than n/3 times are rare. There can be at most two such elements. For each unique element, we count its occurrences and check if it exceeds n/3. We use a set to avoid adding duplicates to the result.

Algorithm

For each element num in the array:
- Count how many times num appears.
- If the count exceeds n / 3, add it to the result set.
Convert the set to a list and return.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        res = set()
        for num in nums:
            count = sum(1 for i in nums if i == num)
            if count > len(nums) // 3:
                res.add(num)
        return list(res)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ since output array size will be at most $2$ .

2. Sorting

Intuition

After sorting, identical elements are grouped together. We can scan through and count consecutive runs of each element. If a run's length exceeds n/3, we add that element to our result. This approach avoids the nested loops of brute force.

Algorithm

Sort the array.
Use two pointers i and j to identify consecutive groups of equal elements.
For each group, if j - i > n / 3, add the element to the result.
Move i to j and repeat until the array is exhausted.
Return the result list.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        nums.sort()
        res, n = [], len(nums)

        i = 0
        while i < n:
            j = i + 1
            while j < n and nums[i] == nums[j]:
                j += 1
            if (j - i) > n // 3:
                res.append(nums[i])
            i = j

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Frequency Count

Intuition

We can count each element's frequency in a single pass using a hash map. Then we iterate through the map and collect all elements whose count exceeds n/3. This trades space for time compared to the brute force approach.

Algorithm

Build a frequency map by counting occurrences of each element.
Iterate through the map entries.
For each entry with count greater than n / 3, add the element to the result.
Return the result list.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        count = Counter(nums)
        res = []

        for key in count:
            if count[key] > len(nums) // 3:
                res.append(key)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Boyer-Moore Voting Algorithm

Intuition

The Boyer-Moore algorithm extends to finding up to two majority elements. We maintain two candidates with their counts. When we see a candidate, we increment its count. When we see a different element and both counts are positive, we decrement both. When a count is 0, we replace that candidate. After one pass, we verify the candidates by counting their actual occurrences.

Algorithm

Initialize two candidates num1, num2 and their counts cnt1, cnt2 to 0.
For each element:
- If it matches num1, increment cnt1.
- Else if it matches num2, increment cnt2.
- Else if cnt1 == 0, set num1 = num and cnt1 = 1.
- Else if cnt2 == 0, set num2 = num and cnt2 = 1.
- Else decrement both counts.
Count actual occurrences of both candidates.
Add candidates with count greater than n / 3 to the result.
Return the result.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        num1 = num2 = -1
        cnt1 = cnt2 = 0

        for num in nums:
            if num == num1:
                cnt1 += 1
            elif num == num2:
                cnt2 += 1
            elif cnt1 == 0:
                cnt1 = 1
                num1 = num
            elif cnt2 == 0:
                cnt2 = 1
                num2 = num
            else:
                cnt1 -= 1
                cnt2 -= 1

        cnt1 = cnt2 = 0
        for num in nums:
            if num == num1:
                cnt1 += 1
            elif num == num2:
                cnt2 += 1

        res = []
        if cnt1 > n // 3:
            res.append(num1)
        if cnt2 > n // 3:
            res.append(num2)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since output array size will be at most $2$ .

5. Boyer-Moore Voting Algorithm (Hash Map)

Intuition

This variation uses a hash map to track candidates instead of fixed variables. We allow at most 2 elements in the map. When a third element tries to enter, we decrement all counts and remove elements with count 0. This generalizes the Boyer-Moore approach and can be extended to find elements appearing more than n/k times.

Algorithm

Create a hash map to store candidate counts.
For each element, increment its count in the map.
If the map has more than 2 entries:
- Decrement all counts by 1.
- Remove entries with count 0.
After processing, verify each remaining candidate by counting its actual occurrences.
Return candidates with count greater than n / 3.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        count = defaultdict(int)

        for num in nums:
            count[num] += 1

            if len(count) <= 2:
                continue

            new_count = defaultdict(int)
            for num, c in count.items():
                if c > 1:
                    new_count[num] = c - 1
            count = new_count

        res = []
        for num in count:
            if nums.count(num) > len(nums) // 3:
                res.append(num)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since output array size will be at most $2$ .

Common Pitfalls

Skipping the Verification Pass

The Boyer-Moore voting algorithm only identifies candidates that might appear more than n/3 times. After the first pass, you must verify each candidate by counting its actual occurrences. Skipping this step returns incorrect results when candidates do not actually exceed the threshold. This verification pass is essential, not optional.

Using Wrong Threshold Comparison

The problem asks for elements appearing more than n/3 times, meaning strictly greater than (>), not greater than or equal to (>=). Using count >= n/3 includes elements that appear exactly n/3 times, which is incorrect. Be precise with the comparison operator.

Incorrect Candidate Selection Order

When implementing Boyer-Moore with two candidates, the order of conditions matters. You must first check if the current element matches an existing candidate before checking if a slot is empty. If you check for empty slots first, you might assign the same element to both candidate slots, wasting one slot and missing potential majority elements.