Majority Element

ArrayQuick Select
https://leetcode.com/problems/majority-element

# Solution

Let nn be the length of the array nums.

# 1-liner Cheating

# HashMap

Return the element w/ max count.

Complexity

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

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

# Sort

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

Complexity

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

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

# Quick Select

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

Complexity

time: O(n)O(n)
space: O(logn)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)

# Follow Up

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

# Boyer-Moore Voting Algorithm

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

Complexity

time: O(n)O(n)
space: O(1)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