In this article we take a look at LeetCode question #169: Majority Element and solve it in 3 different ways using JavaScript 🔥. Check out the original question and explanation here .

Solution 1: Brute Force

From the problem, we can define the majority element as the element that appears more than [n/2] times where n is the size of the input array nums. In this solution, our goal is to track the number of occurrences of each element in the array by brute force.

We can do this by looping through nums and for each element, looping through nums again. Our goal here is to compare our current element to the rest of the array. If the elements from the two loops match, we increment its occurrence. Once we find an element whose occurrence is greater than [n/2] (half the total number of elements in the input array), we can return that element.

Pseudocode

// define half the total number of elements from nums.
// first check if there is only one input. if so, return the input.
// loop through nums and declare a counter:
    // loop through nums a second time and compare the elements from both loops:
        // if the elements from both loops are the same value, we increment our counter.
        // this keeps track of the number of occurrences of each element in nums
    // if our counter is greater than [n/2] we can return that element
// otherwise there is no majority element and we return -1;

Solution 1

function majorityElement1(nums) {
  // define half the total number of elements from nums.
  let halfCount = nums.length / 2;
  // first check if there is only one input. if so, return the input.
  if (nums.length === 1) return nums[0];
  // loop through nums and declare a counter.
  for (let num of nums) {
    let counter = 0;
    // loop through nums a second time and compare the elements from both loops.
    for (let elem of nums) {
      // if the elements from both loops are the same value, we increment our counter.
      // this keeps track of the number of occurrences of each element in nums
      if (num === elem) counter++;
    }
    // if our counter is greater than [n/2] we can return that element
    if (counter > halfCount) return num;
  }
  // otherwise there is no majority element and we return -1;
  return -1;
}

// test cases:
console.log(majorityElement1([3, 2, 3])); // 3
console.log(majorityElement1([4, 3, 3, 5])); // -1

Time complexity: O(n^2). The two nested for loops in this solution result in a quadratic time complexity.

Space complexity: O(1). No additional space needs to be allocated in this solution.

Solution 2: HashMap - One Loop

Just like in the previous solution, we can define the majority element as the element that appears more than [n/2] times where n is the size of the input array nums. In this solution, our goal is to loop over nums and build a HashMap to map each element to its number of occurrences. We can then return the element that fits the majority element definition.

Pseudocode

// define half the total number of elements from our input array.
// declare our map.
// first check if there is only one input. if so, return the input.
// loop through nums: 
    // if num exists on map, increment its value. 
    // otherwise, we add num as a new key with an initial value of 1. 
    // check if the value of num is greater than [n/2]: 
        // if so, return num
// otherwise, there is no majority element and we return -1.

Solution 2

function majorityElement2(nums) {
  // define half the total number of elements from our input array.
  let halfCount = nums.length / 2;
  // declare our map.
  const map = {};
  // first check if there is only one input. If so, return the input.
  if (nums.length === 1) return nums[0];
  // loop through nums 
  for (let num of nums) {
    // if num exists on map, increment its value.
    if (map.hasOwnProperty(num)) {
      map[num] += 1;
    } else {
      // otherwise, we add num as a new key with an initial value of 1. 
      map[num] = 1;
    }
    // check if the value of num is greater than [n/2] 
    if (map[num] > halfCount) {
      // if so, we return the key.
      return num;
    }
  }
  // otherwise, there is no majority element and we return -1.
  return -1;
}

// test cases:
console.log(majorityElement2([3, 2, 3])); // 3
console.log(majorityElement2([4, 3, 3, 5])); // -1

Time complexity: O(n). We iterate over nums once and make a HashMap insertion for each element in constant time. This results in an O(n) time complexity for this solution where the time is proportional to the size of nums.

Space complexity: O(n). The size of our HashMap is proportional to the size of nums.

Solution 3: HashMap - Two Loops

This solution is similar to Solution #2 except we use two loops: one to build our HashMap and another to search our map for the majority element.

Pseudocode

// define half the total number of elements from our input array .
// declare our map.
// loop through nums and determine whether to add a key to map or increment a keys' value:
    // if num exists on map, increment it's value.
    // otherwise, we add num as a new key with an initial value of 1. 
// loop through our maps' keys and evaluate which keys' value is greater than halfCount:
    // if our keys' value is greater than [n/2], we return that key.
// if there is no majority element in the input, we return -1.

Solution 3

function majorityElement3(nums) {
  // define half the total number of elements from our input array.
  let halfCount = nums.length / 2;
  // declare our map.
  const map = {};
  // loop through nums and determine whether to add a key to map or increment a keys' value.
  nums.forEach((num) => {
    // if num exists on map, increment it's value.
    if (map.hasOwnProperty(num)) {
      map[num] += 1;
    } else {
      // otherwise, we add num as a new key with an initial value of 1.
      map[num] = 1;
    }
  });
  // loop through our maps' keys and evaluate which keys' value is greater than halfCount.
  for (let elem in map) {
    // if our keys' value is greater than [n/2], we return that key.
    if (map[elem] > halfCount) {
      return elem;
    }
  }
  // if there is no majority element in the input, we return -1.
  return -1;
}

// test cases:
console.log(majorityElement3([3, 2, 3])); // 3
console.log(majorityElement3([4, 3, 3, 5])); // -1

Some things to note from this solution:

• We can use a forEach loop for our first loop since we are trying to loop through nums entirely to map the elements to their occurrences. We are not trying to return any values in this step.
• We can use a for...in loop for our second loop so we can easily loop through our maps keys and return the appropriate one.

Time complexity: O(n). The two for loops in our solution result in a O(2n) time complexity; however, since our solution is still linear (time proportional to number of entries in nums), we can simply express this as O(n).

Space complexity: O(n). Like the previous solution, the size of our HashMap increases with the size of our input array

Summary

This is a great question that can easily be solved with brute force but also through more efficient means such as by implementing a HashMap. This question strengthened my own knowledge of HashMap implementations in JavaScript! In the next post, we will explore how to solve this coding challenge in O(n) time and O(1) space by implementing the Boyer-Moore Majority Vote Algorithm.

You can find the github repo for this solution here and you can also check out my latest projects here. Feel free to follow me on Twitter where I tweet about all things #webdev and don't forget to subscribe to my newsletter so you won't miss out on new content ⚡️.