Plain, simple, efficient C++ code with Explanatory Comments - No fancy code show-off


  • 0
    R

    This question is quite similar to Majority element I. Here, the only trick is to realize that there can be at most 2 majority elements which satisfy the given condition. Then applying the same counting algorithm on any two different candidates as follows:

    vector<int> majorityElement(vector<int>& nums) {
            vector<int> res; // Result vector of majority number if they exist. There can be at most 2 majority elements.
            if(nums.size() > 0) { // nums must be non-empty
                if(nums.size() == 1) res.push_back(nums[0]);
                else {
                    int maj1 = INT_MIN, maj2 = INT_MAX; // initialize majority elements
                    int ct1 = 0, ct2 = 0; // initialize their counts
                    for(int i = 0; i < nums.size(); i++) {
                        if(nums[i] == maj1) ct1++; // If maj1 is found increase its count
                        else if(nums[i] == maj2) ct2++; // If maj2 is found increase its count
                        else if(ct1 == 0) { // maj1 is not valid
                            maj1 = nums[i]; // Assign the current number to maj1
                            ct1++; // Update the maj1`s count
                        }
                        else if(ct2 == 0) { // maj2 is not valid
                            maj2= nums[i]; // Assign the current number to maj2
                            ct2++; // Update the maj2`s count
                        }
                        else { // The current number is not equal to any of the majority elements candidates
                            ct1--; 
                            ct2--;
                        }
                    }
                    ct1 = 0; // Initialize the counts of the candidates 
                    ct2 = 0; // because we will count them to check validity of "greater than floor(n/3)" condition
                    for(int i = 0; i < nums.size(); i++) {
                        if(nums[i] == maj1) ct1++;
                        else if(nums[i] == maj2) ct2++;
                    }
                    int floorN3 = nums.size()/3; // Calculate this number only once and use it for both counters
                    if(ct1 > floorN3) res.push_back(maj1);// If maj1 satisfies the condition
                    if(ct2 > floorN3) res.push_back(maj2);// If maj2 satisfies the condition
                }
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.