# Solving Majority Element Challenge ### Problem: [169\. Majority Element](https://leetcode.com/problems/majority-element/) Given an array `nums` of size `n`, return *the majority element*. The majority element is the element that appears more than \*`⌊n / 2⌋` , times. You may assume that the majority element always exists in the array. \* `⌊n⌋` means the [floor](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/floor) of n **Example 1:** ```plaintext Input: nums = [3,2,3] Output: 3 Explanation: n = 3, ⌊n / 2⌋ = 1. 3 appears twice which is greater than ⌊n / 2⌋ ``` **Example 2:** ```plaintext Input: nums = [2,2,1,1,1,2,2] Output: 2 Explanation: n = 7, ⌊n / 2⌋ = 3. 2 appears four times which is greater than ⌊n / 2⌋ ``` 1. ## My initial solution: Using an object to keep track of frequencies. ```javascript const majorityElement = function(nums) { //create a frequency object const freqObj = nums.reduce((accum, curr) => { accum[curr] = ( accum[curr] | 0 ) + 1; return accum; }, {}); //find the highest frequency const highestFreq = Math.max(...Object.values(freqObj)); //loop through the frequency object and find the number //that appears the most and return it for (let num in freqObj){ if (freqObj[num] === highestFreq){ return Number(num); } } } ``` This problem uses a hashmap (an object) which keeps track of the frequencies of the numbers in `nums`. ### Bugs I came across while coding this solution 1. Forgot to return `accum` inside the callback passed to the reduce function. * This doesn’t work because the reduce callback needs to pass the accumulator `(accum)` to the next iteration. Without a returned value, `undefined` is passed along. 2. Didn’t parse the final result into a number. * When the numbers are stored in the frequency object they are stored as strings because keys are coerced into strings in Javascript. We need to return a number, so I parse the result back into a number. ### Space and Time Complexity We loop twice, once through the array, and again through the frequency object. In the worst case the **time complexity** is `O(N) + O(M) = O(N)`, where `N` is the length of the array nums, and `M` is the number of keys in `freqObj`. **Note**: `M <= N.` I use an object to store the keys so the **space complexity** is `O(N)` where `N` is the number of keys in `freqObj`. 2. ## Sorting the nums first ```javascript const majorityElement = function(nums) { //sort the numbers in place nums.sort((a, b) => a - b); //return the number in the middle of the nums array return nums[Math.floor(nums.length / 2)]; }; ``` This is such a cool solution. My mentor, Michael Kazin, showed it to me and my mind was blown. It makes so much sense once you see it. Because we always have a number that appears more than half the length of the array, if you sort the array, the number in the middle after sorting will be the majority element 🤯. ### Space and Time Complexity The above solution perfectly illustrates that a short solution isn’t always optimal. From MDN: [The time and space complexity of the sort cannot be guaranteed as it depends on the implementation.](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort) We can assume that on average the **time complexity** is `N(logN)` where `N` is the length of the nums array. 3. ## Moore’s Voting Algorithm Shout-out to Michael Kazin for helping me understand this solution. ### **The idea behind the solution** * Lets assume `nums` is the array below. ```javascript let nums = [2,2,1,1,1,2,2] ``` * Take the majority element, 2 in this case, and replace it with all 1s. * Replace everything else with -1. * Because 2 is the majority element here, the number of 1s will be greater than the number of -1s and the total sum will be positive. * That’s the premise of the solution. But we do this in a loop, while keeping track of which element results in an overall positive sum. ### **The Actual algorithm :** * Loop through the `nums` array * Keep track of two variables `result` and `majority`. * Result will store the `majority` element and `majority` will keep track of the majority element‘s current “count.” * When the current element in the loop **is equal** to result, **increment** `majority` by 1. * If the current element **is not equal** to result, decrement `majority` by 1. * If `majority` becomes 0 switch result. As you loop through the array you are tracking the element that is the majority amongst all the elements to the left of the current number in the iteration including itself. At the end of the loop, the majority element wins the tug of war. ```javascript const majorityElement = function(nums) { //lets start with the majority element being the //first number in nums. let result = nums[0]; //start majority count at 0 let majority = 0; //loop through the array for (let i = 0; i < nums.length; i++){ let currentNum = nums[i]; //if majority count is not 0 //increment majority count if the current # is equal to result //decrement if not if (majority != 0){ majority += currentNum === result ? 1 : -1; } //if majority count is 0, then let result be currentNum and //increment majority else{ result = currentNum; majority++; } } //finally return result return result; }; ``` ### Bugs I came across while coding this solution Pseucode and talking through the solution was very important! 1. Even after all the hard work, I made the mistake of not following my own pseudocode, and had to backtrack. 2. Not incrementing `majority` in the else statement * If we dont increment `majority` inside the else statement, then whenever `majority` is 0, we just reassign result, but the currentNum’s “vote” during that iteration won’t be counted towards `majority`. We call that election rigging.🥁 ### Space and Time Complexity We loop through the `nums` array once, and don’t use any significant extra storage. Time complexity is `O(N)` where `N` is the length of the `nums` array and space complexity is `O(1)`. And there you have it!!! Solutions to the majority element problem. Share your solutions, or any questions/feedback you have!