Given an array a, find the majority element in it without using any extra space.
It's guaranteed that there is always a majority element present in the array.
A majority element is the element that's present more than n/2 times in the array.
a = [1, 2, 3, 1, 1]
answer = 1
This problem can be solved in an interesting way using the greedy approach.
The idea is that, for the element that's present in the majority, all other elements combined will still not be able to cancel out this element.
1. Start off by assuming that the first element is the majority element.
2. If the next element is same as the current element, increment the counter.
3. If not, decrement the counter.
4. If the counter reaches zero, set the current item as the majority element.