Majority Element Leetcode Solution

Problem Statement

We are given an array of integers. We need to return the integer which occurs more than ⌊N / 2⌋ time in the array where ⌊ ⌋ is the floor operator. This element is called the majority element. Note that the input array always contains a majority element.

Example

Array = {1 , 3 , 3 , 3}

3

Exaplanation: ⌊N / 2⌋ = 4 / 2 = 2. And the integer '3' occurs 3 times in the array.

Array = {1 , 1 , 2}

1

Explanation: ⌊N / 2⌋ = ⌊3 / 2⌋ = 1. And '1' occurs 2 times in the array.

Approach(Hashtable)

We can store the frequency of every element in the array in a hash table. It then becomes easy to check for an integer having frequency > ⌊N / 2⌋.

Algorithm

 

- Initialize a hash table to store the frequency of integers in the array: frequency

- For every element, i, in the array:

 

- Increment frequency or set frequency = 0 if it is not in the table already

- If frequency > N / 2:

 

- return i

 

- Return -1 (to avoid compilation error)

- Print the result

 

Implementation of Majority Element Leetcode Solution

C++ Program

#include

using namespace std;

 

int majorityElement(vector &a)

{

int majorityCount = ((int) a.size()) / 2;

unordered_map frequency;

for(int &i : a)

{

if(++frequency > majorityCount)

return i;

}

return -1;

}

 

int main()

{

vector a = {1 , 1 , 2 , 2 , 1 , 2 , 2};

cout

 

www.tutorialcup.com/leetcode-solutions/majority-element-l...

Done