LeetCode Solutions Blog

Majority Element II

Number: 229

Difficulty: Medium

Paid? No

Problem Description

Given an integer array nums, find all elements that appear more than ⌊ n/3 ⌋ times in the array.

Key Insights

There can be at most 2 elements that appear more than ⌊ n/3 ⌋ times.
A modified Boyer-Moore Voting Algorithm can be applied to track at most two potential candidates in one pass.
A second pass is needed to validate the candidates count.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution uses a modified Boyer-Moore Voting Algorithm. Since an element must appear more than ⌊ n/3 ⌋ times to be valid, there can be at most two such candidates.

First, iterate through the array to select up to two candidates based on vote counts.
Then, re-iterate through the array to count the frequency of the selected candidates.
Finally, output the candidates that meet the threshold.
This approach ensures linear time complexity and constant extra space.

Code Solutions

# Function to find all majority elements appearing more than n/3 times
def majorityElement(nums):
    # Initialize candidate and counters for two possible majority elements
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0

    # First pass: find potential candidates
    for num in nums:
        if candidate1 == num:
            count1 += 1
        elif candidate2 == num:
            count2 += 1
        elif count1 == 0:
            candidate1 = num
            count1 = 1
        elif count2 == 0:
            candidate2 = num
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1

    # Second pass: validate the candidates
    result = []
    count1 = count2 = 0
    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1

    n = len(nums)
    if count1 > n // 3:
        result.append(candidate1)
    if count2 > n // 3:
        result.append(candidate2)
    return result

# Example usage:
print(majorityElement([3,2,3]))  # Output: [3]