# LeetCode: Majority Element Solution

*Boyer-Moore Voting Algorithm*

Find element that appears more than

## Approach: Sorting

Sort the array. Since the element appears more than

Complexity:

- Time: O(nlogn)
- Space: O(1)orO(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 )67 let [res, max] = [0, 0]89 for (const [num, occurence] of numOccurenceMapping) {10 if (max < occurence) {11 max = occurence12 res = num13 }14 }1516 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]34 for (const num of nums) {5 if (count === 0) {6 res = num7 count++8 } else {9 count += res === num ? 1 : -110 }11 }1213 return res14}

## Comments

Loading comments...

## Tags

leetcode

array

sorting

hash table

## Apply and earn a $2,500 bonus once you're hired on your first job!

Clients from the Fortune 500 to Silicon Valley startups

Choose your own rate, get paid on time

From hourly, part-time, to full-time positions

Flexible remote working environment

A lot of open JavaScript jobs!!

**Fact corner:** Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.

**Still hesitate?** Read HoningJS author's guide on dealing with Toptal interview process.