algoadvance

LeetCode Problem 229: Majority Element II

Given an integer array nums of size n, find all elements that appear more than ⌊ n / 3 ⌋ times. You must do this in O(n) time and O(1) space.

Clarifying Questions

  1. Q: What should be returned if no elements meet the condition? A: An empty list should be returned.

  2. Q: Can the input array contain negative numbers? A: Yes, the integers can be negative.

  3. Q: Should the results be returned in any specific order? A: No specific order is required for the results.

Strategy

This problem can be effectively solved using the Boyer-Moore Voting Algorithm for finding multiple majority elements. The algorithm is based on the idea of maintaining counters for potential majority elements and then validating those candidates.

Steps:

  1. Identify Potential Candidates:
    • We initialize two candidate variables and their respective counters.
    • Traverse through the array and update these candidates and counters based on the element being processed.
  2. Count and Verify:
    • After identifying potential candidates, count their occurrences to verify if they appear more than ⌊ n / 3 ⌋ times.

Code

def majorityElement(nums):
    if not nums:
        return []
    
    # Step 1: Find candidates
    candidate1, candidate2, count1, count2 = None, None, 0, 0
    
    for num in nums:
        if candidate1 == num:
            count1 += 1
        elif candidate2 == num:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = num, 1
        elif count2 == 0:
            candidate2, count2 = num, 1
        else:
            count1 -= 1
            count2 -= 1
    
    # Step 2: Verify candidates
    result = []
    count1, count2 = 0, 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
nums = [3,2,3]
print(majorityElement(nums))  # Output: [3]
nums = [1,1,1,3,3,2,2,2]
print(majorityElement(nums))  # Output: [1, 2]

Time Complexity

The algorithm requires two passes over the input array:

Thus, the time complexity is O(n), where n is the length of the array, as required by the problem statement.

Space Complexity

The space complexity is O(1) because we are only using a constant amount of extra space, regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com