Given an array of size n, find the majority element. The element that appears more than ⌊ n/2 ⌋ times in the array. Note: Input will be a non-empty and unsorted array.

**Example**

```
Input: [2,1,2]
Output: 2
Input: [1,1,2,2,2,1,1]
Output: 1
```

## Solution Approach

## 1. Sorting

On sorting the given array, the element occurring more than [n/2] times will be present at the middle of the array. But, sorting an array takes O(nlog(n)). So the time complexity of this approach becomes nlog(n).

```
#include <algorithm>
class Solution
{
public:
int majorityElement(vector<int> &nums)
{
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};
```

` Runtime: 72 ms Memory: 20.1 MB `

Time Complexity:O(nlog(n))

Space Complexity:O(1)

## 2. Using Hash Map

We can use a Hash Map to iterate through the array for once and then return the array that occurs more than [n/2] times. As we are iterating only once the Time complexity would be O(n) and the hashmap does take extra space of O(n).

```
class Solution
{
public:
int majorityElement(vector<int> &nums)
{
unordered_map<int, int> map;
int n = nums.size();
for (int i = 0; i < n; i++)
{
map[nums[i]]++;
if (map[nums[i]] > n / 2)
return nums[i];
}
return -1;
}
};
```

` Runtime: 48 ms Memory: 20.1 MB `

Time Complexity:O(n)

Space Complexity:O(n)

## 3. Without using Hash Map

Hash Map does take a lot of space but, in this method we cancel out the occurrence of each non-majority element to the majority element. Say, there are 7 elements, there would be 4 majority elements and 3 non-majority elements.

```
class Solution
{
public:
int majorityElement(vector<int> &nums)
{
int count = 0, major;
for (auto a : nums)
{
if (count == 0)
{
major = a;
count = 1;
}
else if (major == a)
{
count++;
}
else
{
count--;
}
}
return major;
}
};
```

` Runtime: 32 ms Memory: 20 MB `

## Complexity for majority element

Time Complexity:O(n)

Space Complexity:O(1), no extra space.