Majority Element

17.10 Majority Element: A majority element is an element that makes up more than half of the items in an array. Given a positive integers array, find the majority element. If there is no majority element, return -1. Do this in 0 (N) time and O( 1) space.

EXAMPLE
Input: 1 2 5 9 5 9 5 5 5
Output: 5

Complexity: O(n) time and O(1) space

The Idea: The majority element of an array is guareenteed to be iterated over floor(n/2) times. Less frequent elements are then filtered out because contrasting elements cancel each other out.

int majorityElement(vector<int>& nums) {
    if (nums.empty()) return -1;

    int maj = nums[0];
    int count = 1;

    for (int i = 1; i < nums.size(); i++) {
        if (!count) {
            maj = nums[i];
            count++;
        }
        else if (nums[i] == maj) count++;
        else count--;

    }
    return maj;
}

int main()
{
    vector<int> t1 = { 1, 2, 5, 9, 5, 9, 5, 5, 5 };
    cout << majority_element(t1);
}