#229

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Majority Element II

Identify all elements in an integer array appearing more than ⌊ n/3 ⌋ times using efficient array scanning and hash counting techniques.

array hash table sorting counting

Problem Statement

Given an integer array of length n, return all elements that appear more than ⌊ n/3 ⌋ times. You must consider arrays where multiple elements can exceed this threshold, but no more than two elements can do so simultaneously due to the n/3 limit.

For example, for nums = [3,2,3], the output is [3] because 3 occurs twice in a length-3 array, exceeding ⌊3/3⌋ = 1. For nums = [1,2], the output is [1,2] since both appear once in length 2, each exceeding ⌊2/3⌋ = 0.

Examples

Example 1

Input: nums = [3,2,3]

Output: [3]

Example details omitted.

Example 2

Input: nums = [1]

Output: [1]

Example details omitted.

Example 3

Input: nums = [1,2]

Output: [1,2]

Example details omitted.

Constraints

1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109

Solution Approach

Hash Map Counting

Scan the array and maintain a hash map to track frequencies. After scanning, iterate through the map and collect keys whose counts exceed n/3. This approach directly applies the array scanning plus hash lookup pattern but uses O(n) space.

Sorting-Based Counting

Sort the array first, then iterate sequentially to count consecutive duplicates. Add any number whose count exceeds n/3 to the result. This uses sorting to simplify counting and handles the n/3 majority logic without extra hash structures.

Boyer-Moore Variant

Maintain up to two candidates with counters since at most two elements can appear more than n/3 times. Scan the array updating candidates and counters; then verify candidates by a second pass. This minimizes space and avoids hash maps, directly reflecting the array scanning plus conditional count pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n) with hash counting or Boyer-Moore to O(n log n) with sorting. Space complexity is O(n) for hash map or O(1) for the Boyer-Moore variant. Sorting uses O(1) extra if in-place, otherwise O(n).

What Interviewers Usually Probe

Expect candidates tracking due to n/3 frequency limit.
Check whether multiple majority elements are possible; signal for Boyer-Moore.
Sorting may simplify counts but discuss time-space trade-offs.

Common Pitfalls or Variants

Common pitfalls

Failing to consider that at most two elements can exceed n/3 and assuming more candidates.
Using hash maps without verifying counts may include false positives.
Incorrect integer division when computing ⌊ n/3 ⌋ can yield off-by-one errors.

Follow-up variants

Majority Element I where n/2 threshold simplifies to single candidate selection.
Find elements appearing more than n/k times for arbitrary k using extended Boyer-Moore.
Count elements exceeding a dynamic frequency threshold instead of fixed n/3.

FAQ

What is the easiest way to find all majority elements for the n/3 threshold?

Use the Boyer-Moore variant keeping up to two candidates and verify counts in a second pass; this avoids full hash maps.

Can sorting alone be used to solve Majority Element II?

Yes, sorting groups identical numbers together, allowing sequential counting, though time becomes O(n log n).

Why is the n/3 limit important for candidate selection?

Because no more than two elements can appear more than n/3 times, so only up to two candidates need tracking.

Does Majority Element II allow negative numbers?

Yes, the algorithm treats all integers the same; counts or candidates are independent of value sign.

Which pattern does this problem best illustrate?

It exemplifies the array scanning plus hash lookup pattern, showing trade-offs between O(n) hash counting and O(1) candidate tracking.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n1 = n2 = 0
        m1, m2 = 0, 1
        for m in nums:
            if m == m1:
                n1 += 1
            elif m == m2:
                n2 += 1
            elif n1 == 0:
                m1, n1 = m, 1
            elif n2 == 0:
                m2, n2 = m, 1
            else:
                n1, n2 = n1 - 1, n2 - 1
        return [m for m in [m1, m2] if nums.count(m) > len(nums) // 3]

Continue Practicing

#169 majority element #347 top k frequent elements #594 longest harmonious subsequence