Majority Element II

LeetCode 229 | Difficulty: Medium

Medium

Problem Description

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

Example 1:

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

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

- `1 <= nums.length <= 5 * 10^4`

- `-10^9 <= nums[i] <= 10^9`

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

Topics: Array, Hash Table, Sorting, Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 213 ms)

Metric	Value
Runtime	213 ms
Memory	44.3 MB
Date	2022-02-08

Solution

public class Solution {
    public IList<int> MajorityElement(int[] nums) {
        int n = nums.Length;
        int count1 = 0, count2 = 0, c1 = 0, c2 = 0;
        foreach(var num in nums)
        {
            if(c1 == num) count1++;
            else if(c2==num) count2++;
            else if(count1 == 0)
            {
                c1 = num;
                count1 += 1;
            }
            else if(count2==0)
            {
                c2 = num; count2++;
            }
            else
            {
                count1--;
                count2--;
            }
        }
        
        List<int> result = new List<int>();
        if(nums.Count(x=>x==c1) > n/3) result.Add(c1);
        if(c1 != c2 && nums.Count(x=>x==c2) > n/3) result.Add(c2);
        
        return result.ToArray();
        
        
    }
}

📜 1 more C# submission(s)

Submission (2022-02-08) — 249 ms, 44.5 MB

public class Solution {
    public IList<int> MajorityElement(int[] nums) {
        int n = nums.Length;
        int count1 = 0, count2 = 0, c1 = 0, c2 = 0;
        foreach(var num in nums)
        {
            if(c1 == num) count1++;
            else if(c2==num) count2++;
            else if(count1 == 0)
            {
                c1 = num;
                count1 += 1;
            }
            else if(count2==0)
            {
                c2 = num; count2++;
            }
            else
            {
                count1--;
                count2--;
            }
        }
        
        List<int> result = new List<int>();
        if(nums.Count(x=>x==c1) > n/3) result.Add(c1);
        if(c1 != c2 && nums.Count(x=>x==c2) > n/3) result.Add(c2);
        
        return result.ToArray();
        
        
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Think about the possible number of elements that can appear more than ⌊ n/3 ⌋ times in the array.

Hint 2: It can be at most two. Why?

Hint 3: Consider using Boyer-Moore Voting Algorithm, which is efficient for finding elements that appear more than a certain threshold.