⚡Flashcard Drill➔
NeetCode #109LC-229MediumArrays & HashingNC 250
← Back to All Problems

#109 · #229 · Majority Element II(多数元素 II)

📌 Problem Statement & Constraints

Given an integer array nums of size n, find all elements that appear more than n / 3 times. Constraints: 1 <= n <= 5 * 10^4, -10^9 <= nums[i] <= 10^9. The solution must run in O(n) time and use O(1) space.

💡 Core Algorithmic Approaches

  1. At most two elements can appear more than n / 3 times, because three such elements would already exceed n.
  2. Extend Boyer-Moore voting to two candidates. Maintain c1, n1 and c2, n2.
  3. For each element x: if x == c1 increment n1; else if x == c2 increment n2; else if n1 == 0 adopt x as c1; else if n2 == 0 adopt x as c2; else decrement both counters.
  4. Unlike the majority case, existence is not guaranteed, so a second pass must count the occurrences of each candidate and filter those exceeding n / 3.

💻 Benchmark Python3 Implementation

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        c1 = c2 = None
        n1 = n2 = 0
        for x in nums:
            if x == c1:
                n1 += 1
            elif x == c2:
                n2 += 1
            elif n1 == 0:
                c1, n1 = x, 1
            elif n2 == 0:
                c2, n2 = x, 1
            else:
                n1 -= 1          # cancel one vote from each candidate
                n2 -= 1
        # mandatory verification: existence is not guaranteed here
        res = []
        for c in (c1, c2):
            if c is not None and nums.count(c) * 3 > len(nums):
                res.append(c)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass for voting plus one pass for verification (nums.count runs twice, each O(n)).
💾 Space Complexity
O(1): four scalar variables. A Counter would be O(n) space and is the naive baseline.

⚠️ Interview Pitfalls & Follow-ups

  • Skipping the verification pass: the algorithm only guarantees that any element exceeding n/3 must be one of the two candidates -- it does not guarantee the candidates qualify.
  • Forgetting the n1 == 0 / n2 == 0 branches: without them, an element can never become a new candidate once both slots are taken.
  • Decrementing only one counter in the cancel branch: both must be decremented; this is what makes the two-candidate version work.
  • Allowing the same value to occupy both candidate slots: initialising them to None and using elif chains prevents this.
  • Assuming exactly two answers: the result can contain zero, one or two elements.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems