LeetCode: Majority Element Solution
Boyer-Moore Voting AlgorithmFind 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.