We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Majority Element II

Difficulty: Medium

Problem Description

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

Key Insights

  • An element appears more than n/3 times if it is a "majority" element.
  • There can be at most two majority elements since if there were three, they would each have to appear more than n/3 times, which is impossible.
  • We can utilize a modified version of the Boyer-Moore Voting Algorithm to efficiently find these elements.

Space and Time Complexity

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

Solution

To solve the problem, we use a two-pass algorithm. In the first pass, we identify up to two potential majority candidates using a counter mechanism. In the second pass, we verify if these candidates do indeed appear more than n/3 times. This approach ensures we only use constant space and achieve linear time complexity.

  1. First Pass: Use two variables to keep track of the candidates and their counts.
  2. Second Pass: Count the occurrences of these candidates to confirm if they appear more than n/3 times.

Code Solutions

def majorityElement(nums):
    if not nums:
        return []
    
    candidate1, candidate2, count1, count2 = None, None, 0, 0
    
    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = num, 1
        elif count2 == 0:
            candidate2, count2 = num, 1
        else:
            count1 -= 1
            count2 -= 1

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

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

    return result
← Back to All Questions