Majority Element

The idea is to count the number of times each element occurs and if any element occurs more than N/2 times, then include it in our answer.

Steps are as follows :

1. Create a variable to store the maximum count, let’s say “count”.
2. Traverse through the given array/list from start to the end.
3. While Iterating through the array, pivot each element one by one.
4. Initialise a variable “count” to 0 and iterate through the array once again.
5. If you find an element whose value is equal to the pivoted element, then increment “count” by 1.
6. After iterating through the array if the value of “count” is more than N/2, then return that element as the answer.

The idea is to sort the array and then count the number of occurrences of each element in a single traversal.

Steps are as follows:

1. Sort the array in non-decreasing order.
2. As soon as we have a sorted array/list, we can say that the majority element is nothing but the middle element of the sorted array/list.
3. Now you might be wondering why? It’s already given in the question that a majority element always exists. So think of it as a window of size ceil(N/2) and whenever we slide the window from starting to the end position then there always exists the middle element of our array/list in the window and that middle element is the majority element. For example: ARR = [ 2 3 1 2 2 2 ]

Sorted ARR = [1 2 2 2 2 3]

So for window size ceil (N/2) which is 4, the middle element of the sorted array/list is always present in the window and that element is the majority element, which is 2 in our example.

Our intuition is to store the frequency of elements from the given array/list into the HashMap. And whenever the count is greater than half of the number of elements of the given array/list, return that key which is actually the majority element. 

Steps are as follows :

1. Create a HashMap to store a key-value pair, which stores elements of the array/list as the key and value as the frequency of that element in the given array/list.
2. Traverse the given array/list from start to the end.
3. For every element in the given array/list, increment the frequency corresponding to that element into the HashMap.
4. When the frequency of any element will be greater than half of the number of elements in the given array/list, then return that element as the majority element.

In the given array/list, we can realise that there can be at most one element that occurs more than floor(N/2) times in the given array/list. Building on that logic, this can be solved using Moore's voting algorithm.

Steps are as follows:

1. The basic idea of the algorithm is if we cancel out each occurrence of an element of the given array/list (let’s say “NUM”) with all the other elements that are different from “NUM” then “NUM” will exist till the end if it is a majority element.
2. We traverse through each element in the given array/list and maintain a count of the element that has the potential of being the majority element.
3. If the next element is the same as the current element then increment the count by 1, otherwise decrement the count by 1.
4. If the count reaches 0, then update the potential index to the current element and set count to 1.