## 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]
``````