LeetCode: Majority Element Solution

Approach: Sorting

Sort the array. Since the element appears more than n / 2 times, take the middle element as the result

Complexity:

• Time: O(nlogn)
• Space: O(1) or O(n) based on input

Implementation

1var majorityElement = function (nums) {
2  return nums.sort((a, b) => a - b)[Math.floor(nums.length / 2)]
3}

Approach: Hash Table

Build a hash table with key-value pairs of number and its occurence

Find the number with maximum occurrence

Complexity:

• Time: O(n)
• Space: O(n)

Implementation

1var majorityElement = function (nums) {
2  const numOccurenceMapping = nums.reduce(
3    (acc, el) => acc.set(el, (acc.get(el) || 0) + 1),
4    new Map()
5  )
6
7  let [res, max] = [0, 0]
8
9  for (const [num, occurence] of numOccurenceMapping) {
10    if (max < occurence) {
11      max = occurence
12      res = num
13    }
14  }
15
16  return res
17}

Approach: Boyer-Moore Voting Algorithm

This is art. Let's see how they do it in one pass in their original explaination

Complexity:

• Time: O(n)
• Space: O(1)

Implementation

1var majorityElement = function (nums) {
2  let [res, count] = [null, 0]
3
4  for (const num of nums) {
5    if (count === 0) {
6      res = num
7      count++
8    } else {
9      count += res === num ? 1 : -1
10    }
11  }
12
13  return res
14}