Find the Element that occurs more than N/2 times

In this article, we will be solving a commonly asked question on arrays, which is the Majority Element problem. In this problem, we are given an array of N integers. Our goal is to find the element that appears more than N/2 times in the array.

Example:

N = 6 Arr = [2, 2, 0, 2, 3, 2] 

Output: 2 

The number 2 has appeared 4 times, which is more than half of 6 i.e. the size of the array.

Solution:

Explanation:

• Initially we use an unordered map to store the frequency of each element as we iterate through the array.

• For each element in the array, we increment its occurrence and store it in the map.

• After counting the frequencies, we iterate through the map to check if any element has a frequency greater than N/2.

• If such an element is found, we return it as the majority element else we return -1.

Time Complexity: O(n)

Space Complexity: O(n)