# LeetCode: Majority Element Solution

Boyer-Moore Voting Algorithm

Find element that appears more than

n / 2
times

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

`.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var 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 = occurence12      res = num13    }14  }15
16  return res17}```

## 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 = num7      count++8    } else {9      count += res === num ? 1 : -110    }11  }12
13  return res14}```

leetcode

array

sorting

hash table

## Next Post

LeetCode: Summary Ranges

Aug 31, 2021

Straight forward checking

## Previous Post

LeetCode: Pascal's Triangle

Aug 29, 2021

How to write Pascal Triangle in plain JavaScript

Search Posts