C++: Majority Element

Thought Process

To find the majority element in an array (an element that appears more than n/2 times), we can use the Boyer-Moore Voting Algorithm. This algorithm is efficient and works in linear time. We maintain a candidate for the majority element and a count. As we iterate through the array, we update the count based on whether the current element matches the candidate. If the count drops to zero, we replace the candidate with the current element. This approach ensures that the candidate at the end of the iteration is the majority element. 

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        int majorityElement = -1;
        int cnt = 0;

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

            if(nums[i] == majorityElement){
                cnt++;
            }
            else if(cnt==0){
                majorityElement = nums[i];
                cnt = 1;
            }
            else 
                cnt--;
        }
        return majorityElement;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array once, making it linear in time complexity. Each operation within the loop is constant time.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, as it only stores a few variables for tracking the candidate and its count.

Code copied!