Solving Majority Element Challenge

Problem: 169. 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 of n

Example 1:

Input: nums = [3,2,3]
Output: 3
Explanation: 
   n = 3, ⌊n / 2⌋ = 1. 
   3 appears twice which is greater than ⌊n / 2⌋

Example 2:

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.

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

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

    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.

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!