## Problem Statement

### Description

Given an array `nums`

of size `n`

, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋`

times. You may assume that the majority element always exists in the array.

### Examples

#### Example 1:

```
Input: nums = [3,2,3]
Output: 3
```

#### Example 2:

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

### Constraints

`n == nums.length`

`1 <= n <= 5 * 104`

`-109 <= nums[i] <= 109`

## Key Insights

There are many different ways to solve this problem. We’ll take a look at two of the simplest approaches. We can use a **hash map** to keep track of the frequency of each number or we could sort the list and return the middle value.

Note: Since we know that the *majority element* appears more than `n/2`

times in the list, we know that it will make up more than 50% of the elements in the array. Consequently, the middle element `n//2`

will always be the *majority element*.

## Python Solution

### Hash Map Solution

```
from collections import Counter
class Solution:
def majorityElement(self, nums: List[int]) -> int:
"""
T: O(N)
S: O(N)
"""
n = len(nums)
mp = Counter(nums)
for number, frequency in mp.items():
if frequency > (n // 2):
return number
```

### Sorting Solution

```
from collections import Counter
class Solution:
def majorityElement(self, nums: List[int]) -> int:
"""
T: O(N log N)
S: O(1) ~ best case; O(N) ~ worst case
"""
n = len(nums)
nums = sorted(nums)
return nums[n // 2]
```