C++: Majority Element II

Thought Process

To find the majority elements in an array that appear more than n/3 times, we can use the Boyer-Moore Voting Algorithm. This algorithm is efficient and works in linear time. We maintain two potential candidates for majority elements and their respective counts. As we iterate through the array, we update the counts based on whether the current element matches either of the candidates. If the count for a candidate drops to zero, we replace it with the current element. After identifying the candidates, we verify their counts to ensure they indeed appear more than n/3 times. 

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {

        int majorityOne = INT_MIN;
        int majorityTwo = INT_MIN;
        int cnt1 = 0;
        int cnt2 = 0;
        int n = nums.size();

        vector<int> ans;
        for(int i=0;i<nums.size();i++){

            if(nums[i]==majorityOne)
                cnt1++;
            else if(nums[i]==majorityTwo)
                cnt2++;
            else if(cnt1==0){
                majorityOne = nums[i];
                cnt1 = 1;
            }
            else if(cnt2==0){
                majorityTwo = nums[i];
                cnt2 = 1;
            }
            else{
                cnt1--;
                cnt2--;
            }
        }
        cnt1=0;
        cnt2=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==majorityOne)
                cnt1++;
            
            if(nums[i]==majorityTwo)
                cnt2++;
        }
        if(cnt1>n/3)
            ans.push_back(majorityOne);
        
        if(cnt2>n/3)
            ans.push_back(majorityTwo);

        return ans;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array twice. The first pass identifies potential majority candidates, and the second pass verifies their counts. Both passes are linear in time complexity.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, as it only stores a few variables for tracking candidates and their counts.

Code copied!