Code Implementation

class Solution:
    def majorityElement(self, nums):
        if not nums:
            return []
        # Boyer-Moore Voting Algorithm extension for n/3 majority
        candidate1 = candidate2 = None
        count1 = count2 = 0

        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

        # Verify the candidates
        result = []
        for c in [candidate1, candidate2]:
            if nums.count(c) > len(nums)//3 and c not in result:
                result.append(c)
        return result
      

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        int candidate1 = 0, candidate2 = 1; // initialize to different values
        int count1 = 0, count2 = 0;

        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        // Verify the candidates
        vector<int> result;
        int cnt1 = 0, cnt2 = 0;
        for (int num : nums) {
            if (num == candidate1) cnt1++;
            else if (num == candidate2) cnt2++;
        }
        if (cnt1 > n / 3) result.push_back(candidate1);
        if (cnt2 > n / 3) result.push_back(candidate2);
        return result;
    }
};
      

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        Integer candidate1 = null, candidate2 = null;
        int count1 = 0, count2 = 0;
        for (int num : nums) {
            if (candidate1 != null && num == candidate1) {
                count1++;
            } else if (candidate2 != null && num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        // Verify the candidates
        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        int cnt1 = 0, cnt2 = 0;
        for (int num : nums) {
            if (candidate1 != null && num == candidate1) cnt1++;
            else if (candidate2 != null && num == candidate2) cnt2++;
        }
        if (cnt1 > n / 3) result.add(candidate1);
        if (cnt2 > n / 3) result.add(candidate2);
        return result;
    }
}
      

var majorityElement = function(nums) {
    let candidate1 = null, candidate2 = null;
    let count1 = 0, count2 = 0;

    for (let num of nums) {
        if (candidate1 !== null && num === candidate1) {
            count1++;
        } else if (candidate2 !== null && num === candidate2) {
            count2++;
        } else if (count1 === 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 === 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    // Verify the candidates
    let result = [];
    let n = nums.length;
    let cnt1 = 0, cnt2 = 0;
    for (let num of nums) {
        if (num === candidate1) cnt1++;
        else if (num === candidate2) cnt2++;
    }
    if (cnt1 > Math.floor(n / 3)) result.push(candidate1);
    if (cnt2 > Math.floor(n / 3)) result.push(candidate2);
    return result;
};
      

Problem Description

Given an integer array nums of size n, return all elements that appear more than ⌊ n/3 ⌋ times. The problem guarantees that the solution must be found in linear time and constant space (excluding the output list).

• Each element in nums can appear any number of times, but you must return all elements that occur more than n/3 times.
• You may assume the input array is not empty.
• There can be up to two such elements in the array.
• Return the answer in any order.

Thought Process

The first instinct might be to use a hash map (dictionary) to count the occurrences of each number, then return those with counts above n/3. This approach is simple and works, but it requires extra space proportional to the number of distinct elements.

However, the problem asks for a solution with constant extra space. That means we cannot store counts for all possible elements. We need a smarter way to track which elements could possibly be majority elements.

Noticing that there can be at most two elements that appear more than n/3 times (since three or more would exceed the array length), we can reduce the problem to tracking at most two candidates. This is a conceptual leap from brute-force counting to a voting algorithm.

Solution Approach

To solve this efficiently, we use an extension of the Boyer-Moore Voting Algorithm. Here's how it works:

1. Candidate Selection:
   • We maintain two candidate variables and their respective counts.
   • As we iterate through the array:
     • If the current number matches one of the candidates, increment its count.
     • If the count for a candidate is zero, set the current number as that candidate and set its count to one.
     • If the current number matches neither candidate and both counts are nonzero, decrement both counts.
2. Verification:
   • After the first pass, the two candidates are possible majority elements. But they may not actually appear more than n/3 times.
   • We do a second pass to count the actual occurrences of each candidate and include them in the result if they exceed n/3.

This works because every time we see a number that doesn't match our candidates and both counts are nonzero, we effectively "cancel out" a vote for each candidate. Only elements that could possibly have enough votes to be a majority will survive this process.

Example Walkthrough

Let's walk through an example with nums = [3,2,3,2,2,1,1,1]:

1. First Pass (Candidate Selection):
   • Start: candidate1 = None, count1 = 0; candidate2 = None, count2 = 0
   • 3: candidate1 = 3, count1 = 1
   • 2: candidate2 = 2, count2 = 1
   • 3: matches candidate1, count1 = 2
   • 2: matches candidate2, count2 = 2
   • 2: matches candidate2, count2 = 3
   • 1: doesn't match either, decrement both counts (count1 = 1, count2 = 2)
   • 1: doesn't match either, decrement both counts (count1 = 0, count2 = 1)
   • 1: candidate1 count is 0, so candidate1 = 1, count1 = 1
2. Second Pass (Verification):
   • Count occurrences of candidates 1 and 2 in the array:
   • 1 appears 3 times, 2 appears 3 times
   • Array length is 8, n/3 = 2.666..., so floor(n/3) = 2
   • Both 1 and 2 appear more than 2 times, so result is [1, 2]

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(n), since we count all elements using a hash map.
  • Space Complexity: O(n), since the hash map could store counts for every unique number.
• Boyer-Moore Voting Algorithm (Optimized):
  • Time Complexity: O(n), as we make two passes through the array (candidate selection and verification).
  • Space Complexity: O(1), since we only use a constant number of variables regardless of input size (excluding the output list).

Summary

The Majority Element II problem challenges us to find all elements in an array appearing more than n/3 times, with strict requirements on time and space. By extending the Boyer-Moore Voting Algorithm, we efficiently track at most two candidates, using constant extra space and linear time. This approach elegantly leverages the mathematical constraint that there can be at most two such elements, making the solution both efficient and insightful.