# Majority Element

ArrayQuick Select

## # Solution

Let $n$ be the length of the array nums.

### # 1-liner Cheating

#### # HashMap

Return the element w/ max count.

Complexity

time: $O(n)$
space: $O(n)$

from collections import Counter
def majorityElement(self, nums: List[int]) -> int:
cnt = Counter(nums)
return max(cnt, key=cnt.get)

1
2
3
4

#### # Sort

As the majority element has more than $\lfloor \dfrac{n}{2} \rfloor$ occurrences, find the $\lfloor \dfrac{n}{2} \rfloor$-th largest element after sorting.

Complexity

time: $O(n \log n)$
space: $O(\log n)$ (can be $O(1)$ if self-implementing Heap Sort)

def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums)//2]

1
2

### # Quick Select

Can also find the $\lfloor \dfrac{n}{2} \rfloor$-th largest element in linear time with randomized algorithm quickSelect.

Complexity

time: $O(n)$
space: $O(\log n)$

def majorityElement(self, nums: List[int]) -> int:
n = len(nums)
return self.quickSelect(nums, 0, n-1, n//2)

def partition(self, arr, left, right):
pivot_idx = randint(left, right)
pivot = arr[pivot_idx]

arr[right], arr[pivot_idx] = arr[pivot_idx], arr[right]
store_idx = left

for i in range(left, right):
if arr[i] < pivot:
arr[i], arr[store_idx] = arr[store_idx], arr[i]
store_idx += 1

arr[right], arr[store_idx] = arr[store_idx], arr[right]
return store_idx

def quickSelect(self, arr, left, right, k):
if left == right:
return arr[left]
pivot_idx = self.partition(arr, left, right)
if k == pivot_idx:
return arr[k]
if k < pivot_idx:
return self.quickSelect(arr, left, pivot_idx-1, k)
else:
return self.quickSelect(arr, pivot_idx+1, right, k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Could you solve the problem in linear time and constant space?

### # Boyer-Moore Voting Algorithm

Increment by $1$ if num == candidate and decrement by $1$ otherwise. Every time cnt becomes $0$, restart the process. At the end, candidate should be the majority element.

Complexity

time: $O(n)$
space: $O(1)$

def majorityElement(self, nums: List[int]) -> int:
cnt = 0
candidate = None

for num in nums:
if cnt == 0:
candidate = num
# increment/decrement cnt
if num == candidate:
cnt += 1
else:
cnt -= 1
return candidate

1
2
3
4
5
6
7
8
9
10
11
12
13