Solving Leetcode’s Majority Element Problem in JavaScript

A step-by-step explanation

The majority element problem has, in my opinion, a bit of an odd, overly complex direction:

Return the majority element of an array, which is the element that appears more than ⌊ n/2 ⌋ times.

I don’t know about the need of calculating which element appears more than 50% of the time. My approach was a bit simpler and more intuitive: the problem is titled “majority element”, so let’s just find the element that appears most in the array, and return that. Let’s get to it.

Let’s say we have an array called nums that looks like this: [3, 2, 3]. Clearly 3 shows up most and that’s what we need to return. How do we do it in code?

A couple of things to keep in mind as we design a solution:

• In order to know which element shows up the most, we’re going to have to iterate through the entire array. There’s just no way around this.
• We’re going to have to figure out a way count how many of each element there is and refer back to this count later in order to know which one is the most frequent flyer in our array.

Thus, iterating and hash maps lend themselves well to help solve this problem.

First, let’s declare our function with an empty object (aka hash map), and frequency counter:

function majorityElement(nums) {
  let numsObj = {};
  let maxFreq = 0;
}

As mentioned, we need to iterate. As we iterate though, let’s populate our numsObj object key:value store following this rule: for each element you see, create a key with a value of 1, unless you’ve seen it before, in which case, just add 1 to its value.

This way, when we iterate through our input array, at the end, we’ll have a neatly organized object that will have all the information we need: which elements are in the array, and how many times it appears. For our example, the numsObj will look like this:

numsObj = {
   2: 1,
   3: 2
}

Next, we’ll have to iterate through our numsObj by checking the values of each key, which is the frequency each number appears in the array. As we do this, we should ask: is this value greater than the maxFreq I’ve seen at this point? If so, I should set the maxFreq to that value. And while we’re at it, we should keep hold of whatever that number it is that shows up most. That’s what this piece of code does:

for (num in numsObj) {
    if (numsObj[num] > maxFreq) {
      maxFreq = numsObj[num];
      maxElement = parseInt(num);
    }
  }

In our example, we first iterate with the number 2, which shows up once. Is 1 greater than the current maxFreq of 0 at which it was initialized? Of course. So we set maxFreq to 1, and maxElement to 2. Note the parseInt() function. That’s just the convert the key in the object back to a number in order to pass the tests.

Next iteration, the number we see is 3. We look up 3 in our numsObj hash to see its value. We see that it’s 2. We compare 2 to the maxFreq in the if statement. Because 2 is greater than the current value of 1, the if statement again evaluates to true, sets MaxFreq to 2, and the maxElement to 3.

We’ve completed iterating through our numsObj hash, and now all that’s left is to return the maxElement: 3. Here’s the full code:

function majorityElement(nums) {
  let numsObj = {};
  let maxFreq = 0;
  let maxElement = null;
for (let num of nums) {
    numsObj[num] = numsObj[num] + 1 || 1;
  }
for (num in numsObj) {
    if (numsObj[num] > maxFreq) {
      maxFreq = numsObj[num];
      maxElement = parseInt(num);
    }
  }
  return maxElement;
}

Thanks for reading!

And remember: grit > talent.