Majority Element - II

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

The steps are as follows:

1. Iterate through the array and pivot each element one by one.
2. Initialize a variable ‘COUNT’ to 0 and iterate through the array once again.
3. If you find an element whose value is equal to the pivoted element, then increment ‘COUNT’ by 1.
4. After iterating through the array if the value of ‘COUNT’ is more than n/3, then store the pivot element if it hasn’t already been included in the answer.
5. Return all the stored elements.

The idea is to store the frequency of each element from the given array/list into the HashMap and then include all the elements with frequencies greater than N/3 in the answer.

Steps are as follows:

1. Iterate through the array and for each element,

• Insert the element into the HashMap if it is not present in the HashMap.
• Otherwise, increment the value corresponding to the current element in the HashMap by 1.

2.Iterate through the HashMap and store all the elements whose frequency is greater than N/3, where ‘N’ is the number of elements in the given array/list.

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

The steps are as follows:

1. Sort the array in non-decreasing order.
2. Iterate through the array and keep a variable ‘COUNT’ to count the occurrences of an element.
3. Increment ‘COUNT’ by 1 if the next element is equal to the current element otherwise reset ‘COUNT’ to 0.
4. If the count for any element is greater than N/3, then include that element in the answer.

The idea is to use a modification of Moore's voting algorithm to find candidate elements that may occur more than N/3 times in the given array. We will use the fact that if we remove 3 distinct elements from the array, the elements which occurred more than N/3 times do not change.

The steps are as follows:

1. We can prove using the pigeonhole principle that there are at most 2 elements possible that can occur more than N/3 times, we will use the variable ‘FIRST_CANDIDATE’ to store the first element that can possibly occur more than ‘N’/3 times and another variable ‘SECOND_CANDIDATE’ to store the second element that can possibly occur more than N/3 times. Also, we will use the variables ‘FIRST_COUNT’ and ‘SECOND_COUNT’, both of which will be initialized to 0, to store the frequency of the ‘FIRST_CANDIDATE’ and ‘SECOND_COUNT’ respectively.
2. Iterate through the array, let’s say our current element is ‘ARR[i]’.
   1. If ‘ARR[i]’ is equal to ‘FIRST_CANDIDATE’ then increment ‘FIRST_COUNT’ by 1
   2. If ‘ARR[i]’ is equal to ‘SECOND_CANDIDATE’ then increment ‘SECOND_COUNT’ by 1.
   3. Otherwise, if ‘FIRST_COUNT’ is equal to 0, set ‘FIRST_CANDIDATE’ equal to ‘ARR[i]’ and increment ‘FIRST_COUNT’ by 1.
   4. Else if ‘SECOND_COUNT’ is equal to 0, set ‘SECOND_CANDIDATE’ equal to ‘ARR[i]’ and increment ‘SECOND_COUNT’ by 1.
   5. Else decrement both ‘FIRST_COUNT’ and ‘SECOND_COUNT’ by 1. By doing this, we are basically removing 3 distinct elements from our array which will not affect the answer.
3. Iterate through the array once again and count the number of occurrences of ‘FIRST_CANDIDATE’ and ‘SECOND_CANDIDATE’.
4. Store ‘FIRST_CANDIDATE’ in the answer if it occurs more than ‘N’/3 times in the given array/list, similarly add ‘SECOND_CANDIDATE’ to the answer if it occurs more than ‘N’/3 times in the given array/list.
5. Return the stored elements.