Majority Element II

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

For example:

1. nums = [3,2,3] should return [3]
2. nums = [1] should return [1]
3. nums = [1,2] should return [1,2]

Constraints:

• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

Could you solve the problem in linear time and in O(1) space?

# Majority Element II

## Problem Description

Given an integer array of size `n`, the task is to find all elements that appear more than `⌊ n/3 ⌋` times. This problem aims to identify elements that have a significant presence in the array. It can be solved efficiently using the Boyer-Moore Majority Vote Algorithm.

## Naive Solution

A naive approach involves iterating through each element in the array and counting its occurrences. If the count of an element is greater than `⌊ n/3 ⌋`, it is added to the result. This approach has a time complexity of O(n^2) because, for each element, we iterate through the array to count its occurrences.

```python
def majority_element_naive(nums):
    n = len(nums)
    result = []
    for num in set(nums):
        count = 0
        for x in nums:
            if x == num:
                count += 1
        if count > n // 3:
            result.append(num)
    return result

Optimal Solution: Boyer-Moore Majority Vote Algorithm

The Boyer-Moore Majority Vote Algorithm can be adapted to solve this problem in linear time and constant space. The algorithm identifies up to two candidate majority elements. A second pass is then used to verify if these candidates appear more than ⌊ n/3 ⌋ times.

def majority_element(nums):
    n = len(nums)
    if n == 0:
        return []

    # Initialize candidates and their counts
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0

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

    # Second pass to verify counts
    count1, count2 = 0, 0
    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1

    result = []
    if count1 > n // 3:
        result.append(candidate1)
    if count2 > n // 3 and candidate1 != candidate2:  # Avoid duplicates
        result.append(candidate2)

    return result

Explanation:

1. Initialization: Initialize two candidate elements (candidate1, candidate2) and their respective counts (count1, count2) to 0.
2. First Pass: Iterate through the array. If an element matches candidate1 or candidate2, increment the corresponding count. If count1 or count2 is 0, assign the current element as a candidate and set its count to 1. If the element doesn't match either candidate and both counts are non-zero, decrement both counts.
3. Second Pass: Reset count1 and count2 to 0. Iterate through the array again to count the actual occurrences of candidate1 and candidate2.
4. Verification: Check if count1 and count2 are greater than ⌊ n/3 ⌋. If they are, add the corresponding candidate to the result. Ensure that duplicate candidates are not added to the result.

Big(O) Runtime Analysis

The optimal solution involves two iterations through the array. The first pass identifies potential candidates, and the second pass verifies their counts. Therefore, the time complexity is O(n) because the algorithm iterates through the array a constant number of times.

Big(O) Space Usage Analysis

The algorithm uses a fixed number of variables (candidate1, candidate2, count1, count2, and the result list), regardless of the input array size. Thus, the space complexity is O(1), indicating constant space usage.

Edge Cases

1. Empty Array: If the input array is empty, the algorithm should return an empty list.
2. Single Element Array: If the input array contains only one element, that element should be returned as it will always appear more than ⌊ n/3 ⌋ times.
3. Two Element Array: If the input array contains two different elements, both elements should be returned since ⌊ 2/3 ⌋ = 0 and both appear more than 0 times.
4. Duplicate Candidates: The algorithm must ensure that duplicate candidates are not added to the result. This is handled by checking candidate1 != candidate2 before adding candidate2 to the result.

Code with Edge Case Handling

The optimal solution provided above already handles most of the relevant edge cases. Here it is again:

def majority_element(nums):
    n = len(nums)
    if n == 0:
        return []

    # Initialize candidates and their counts
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0

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

    # Second pass to verify counts
    count1, count2 = 0, 0
    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1

    result = []
    if count1 > n // 3:
        result.append(candidate1)
    if count2 > n // 3 and candidate1 != candidate2:  # Avoid duplicates
        result.append(candidate2)

    return result