Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Solution: Moore’s Voting Algorithm

Basic idea of the algorithm is if we cancel out each occurrence of a candidate element with all the other elements that are different from candidate then candidate will exist till end if it is a majority element.

Note: This doesn't gurantee that this element will be the majority element, you need to check again.

int majorityElement(vector<int>& nums) {        
    int counter = 0;
    int candidate = nums[0];

    for(auto num: nums) {
        if (counter == 0) {
            candidate = num;
            counter += 1;
        } else {
            counter += candidate == num ? 1 : -1;
        }
    }

    return candidate;
}

Solution: Using Stack

This solution is quite similar to the problem of checking the balance of brackets in a string.

int majorityElement(vector<int>& nums) {
    stack<int> stack;

    for(int i=0; i<nums.size(); i++) {
        if(stack.empty()) {
            stack.push(nums[i]);
        } else {
            if(nums[i] != stack.top()) {
                stack.pop();
            } else {
                stack.push(nums[i]);
            }
        }
    }

    return stack.top();
}