Problem Description

This problem asks you to find all elements in an integer array that appear more than ⌊n/3⌋ times, where n is the size of the array and ⌊n/3⌋ represents the floor division (rounding down to the nearest integer).

For example:

• If the array has 9 elements, you need to find elements appearing more than ⌊9/3⌋ = 3 times
• If the array has 10 elements, you need to find elements appearing more than ⌊10/3⌋ = 3 times
• If the array has 11 elements, you need to find elements appearing more than ⌊11/3⌋ = 3 times

The key insight is that there can be at most 2 elements that appear more than ⌊n/3⌋ times in any array. This is because if 3 elements each appeared more than ⌊n/3⌋ times, their combined count would exceed n, which is impossible.

The solution uses the Boyer-Moore Majority Vote algorithm extended for finding elements that appear more than n/3 times. It maintains two potential candidates (m1 and m2) with their respective counts (n1 and n2). The algorithm processes each element by:

1. Incrementing the count if it matches a candidate
2. Setting it as a new candidate if a candidate slot is empty (count is 0)
3. Decrementing both counts if neither condition is met

After the first pass identifies potential candidates, a second pass verifies which candidates actually appear more than ⌊n/3⌋ times in the array.

Intuition

The key observation is that at most 2 elements can appear more than n/3 times in an array. Why? If 3 or more elements each appeared more than n/3 times, their total count would exceed n, which is impossible.

This constraint leads us to think about tracking just 2 potential candidates. But how do we find these candidates efficiently without using extra space for counting?

The idea comes from the Boyer-Moore Voting Algorithm, which can find a majority element (appearing more than n/2 times) in one pass. The algorithm works by maintaining a candidate and a counter - when we see the candidate, we increment the counter; when we see a different element, we decrement it. When the counter reaches zero, we switch to a new candidate.

For our problem, we extend this to track 2 candidates simultaneously. The intuition is based on a "pairing and cancellation" strategy:

• When we see an element matching one of our candidates, we strengthen that candidate's position by incrementing its count
• When we see a new element and have an empty candidate slot (count = 0), we add it as a potential candidate
• When we see an element that doesn't match either candidate and both slots are occupied, we decrement both counts

Why does this work? Think of it as a survival game where elements compete for dominance. Elements appearing more than n/3 times are so frequent that even if they lose some "votes" to cancellation with other elements, they'll still survive as one of the final two candidates.

The cancellation step (decrementing both counts) essentially removes 3 different elements from consideration - one of each candidate type and the current element. Since any element appearing more than n/3 times must survive this repeated removal of triplets, it will end up as one of our candidates.

Finally, we need a verification pass because our candidates might include elements that don't actually appear more than n/3 times (they just survived the cancellation process). So we count their actual occurrences to confirm.

Solution Approach

The implementation uses the Boyer-Moore Majority Vote algorithm extended for finding up to 2 majority elements. Let's walk through the code step by step:

Initialization:

n1 = n2 = 0        # Counters for the two candidates
m1, m2 = 0, 1      # Two different initial candidates

We initialize two counters n1 and n2 to 0, and two candidates m1 and m2 to different values (0 and 1) to ensure they start as distinct.

First Pass - Finding Candidates:

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

For each element m in the array, we follow this decision tree:

1. If m matches candidate 1 (m1): Increment counter n1
2. Else if m matches candidate 2 (m2): Increment counter n2
3. Else if counter 1 is zero (n1 == 0): Replace m1 with current element m and set n1 = 1
4. Else if counter 2 is zero (n2 == 0): Replace m2 with current element m and set n2 = 1
5. Otherwise: Decrement both counters (n1 and n2) by 1

The order of these conditions is crucial. We first check if the current element matches existing candidates before considering replacement or cancellation.

Second Pass - Verification:

return [m for m in [m1, m2] if nums.count(m) > len(nums) // 3]

After identifying the two potential candidates, we verify which ones actually appear more than n/3 times. We use list comprehension to:

• Iterate through both candidates [m1, m2]
• Count each candidate's actual occurrences using nums.count(m)
• Include only those with count greater than len(nums) // 3

Time and Space Complexity:

• Time: O(n) for the first pass + O(n) for each verification = O(n)
• Space: O(1) as we only use a constant amount of extra variables

The algorithm elegantly handles edge cases like arrays with fewer than 3 elements or arrays where no element appears more than n/3 times, returning an appropriate result in each case.

Example Walkthrough

Let's walk through the algorithm with the array [3, 2, 3, 1, 3, 2, 1, 1] (n = 8, so we need elements appearing more than 8/3 = 2 times).

Initial State:

• m1 = 0, n1 = 0 (candidate 1 and its counter)
• m2 = 1, n2 = 0 (candidate 2 and its counter)

First Pass - Finding Candidates:

After First Pass:

• Candidate 1: m1 = 3 with n1 = 1
• Candidate 2: m2 = 1 with n2 = 1

Second Pass - Verification: Now we count actual occurrences:

• Count of 3: appears 3 times in [3, 2, 3, 1, 3, 2, 1, 1] → 3 > 2 ✓
• Count of 1: appears 3 times in [3, 2, 3, 1, 3, 2, 1, 1] → 3 > 2 ✓

Result: [3, 1] (both elements appear more than ⌊8/3⌋ = 2 times)

The algorithm correctly identified both majority elements. Notice how element 2 (appearing only 2 times) was eliminated through the cancellation process, while elements 3 and 1 (each appearing 3 times) survived as candidates and passed verification.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main parts:

• First pass through the array with the Boyer-Moore voting algorithm: O(n), where each element is visited once with constant time operations (comparisons and arithmetic operations)
• Second pass for verification using nums.count(): This calls count() at most twice (for m1 and m2), and each count() operation takes O(n) time to scan through the entire array

Total time complexity: O(n) + 2 * O(n) = O(n)

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Four integer variables: n1, n2, m1, m2
• The output list contains at most 2 elements (since there can be at most 2 elements that appear more than n/3 times in an array)
• No additional data structures that scale with input size are used

The space complexity remains constant regardless of the input size, making it O(1).

Common Pitfalls

1. Duplicate Candidates in the Result

The most critical pitfall occurs when both candidates end up being the same value, leading to duplicates in the final result. This happens when the array contains only one majority element or when both candidate slots converge to the same value.

Problem Example:

nums = [3, 3, 3]
# After first pass: candidate1 = 3, candidate2 = 3
# Result would be [3, 3] instead of [3]

Solution: Add a check to ensure candidates are distinct before verification:

# Second pass: Verify candidates
threshold = len(nums) // 3
result = []

# Check candidate1
if nums.count(candidate1) > threshold:
    result.append(candidate1)

# Check candidate2 only if it's different from candidate1
if candidate1 != candidate2 and nums.count(candidate2) > threshold:
    result.append(candidate2)

return result

2. Incorrect Initialization of Candidates

Initializing both candidates to the same value (like candidate1 = candidate2 = 0) can cause problems when the array actually contains 0 as an element.

Problem Example:

# Wrong initialization
candidate1 = candidate2 = 0  # Both same value
nums = [0, 0, 0, 1, 2]
# The algorithm may not correctly identify distinct candidates

Solution: Initialize candidates to different values or use None/float('inf'):

# Option 1: Different arbitrary values
candidate1, candidate2 = 0, 1

# Option 2: Use None and check for it
candidate1 = candidate2 = None
# Then modify the conditions to check for None before comparing

3. Inefficient Verification Using count()

Using nums.count() in the verification phase performs a full array scan for each candidate, which could be optimized.

Problem:

# This performs two full scans of the array
for candidate in [candidate1, candidate2]:
    if nums.count(candidate) > threshold:  # O(n) each time

Solution: Count both candidates in a single pass:

# Single pass verification
count1 = count2 = 0
threshold = len(nums) // 3

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

result = []
if count1 > threshold:
    result.append(candidate1)
if count2 > threshold and candidate1 != candidate2:
    result.append(candidate2)

4. Edge Case: Empty Array

Not handling empty arrays can cause errors when accessing candidates or calculating threshold.

Problem Example:

nums = []
# len(nums) // 3 = 0, but the algorithm might still try to process candidates

Solution: Add an early return for edge cases:

def majorityElement(self, nums: List[int]) -> List[int]:
    if not nums:
        return []
  
    if len(nums) <= 2:
        return list(set(nums))  # All elements appear more than n/3 times
  
    # Continue with Boyer-Moore algorithm...