LeetCode 169: Majority Element – JavaScript Solution

📌 Introduction

In this post, we’ll solve LeetCode 169: Majority Element. We’ll cover a straightforward brute-force approach, an optimized solution using the Boyer-Moore Voting Algorithm, and analyze the time and space complexities for each. Code examples will be in JavaScript, with step-by-step explanations.

👉 Original problem link: LeetCode – Majority Element

---

1. Problem Overview

The task is to find the "majority element" in a given array. The majority element is defined as the number that appears more than ⌊n/2⌋ times, where n is the size of the array. You can safely assume that such an element always exists in the input array.

---

2. Example

Input: nums = [2, 2, 1, 1, 1, 2, 2] Output: 2 Explanation: The number 2 appears four times, while the number 1 appears three times. Since 4⌊7/2⌋=3, the majority element is 2.

---

3. Approaches

🔹 Brute Force Approach

• Idea:

  • Use a hash map (or dictionary) to store the frequency of each number in the array.

  • Iterate through the input array once to populate the frequency map.

  • After counting all elements, iterate through the map to find the number with the highest count.

  • This will be the majority element, as it's guaranteed to exist.

Code (JavaScript):

Code snippet

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    const counts = new Map()

    for(const num of nums){
        if(counts.has(num)){
            counts.set(num, counts.get(num) + 1)
        } else {
            counts.set(num, 1)
        }
    }

    let max = null
    for(const [num, count] of counts){
        if(max == null || count > counts.get(max)){
            max = num
        }
    }

    return max

};

Time Complexity = O(N)

Space Complexity = O(N)

---

🔹 Optimized Approach

• Idea:

  • This approach, known as the Boyer-Moore Voting Algorithm, is highly efficient.

  • The core intuition is that the majority element's count is so high that even if every minority element "fights" and cancels out one majority element, the majority element will still be the last one standing.

  • We can simulate this by iterating through the array and maintaining a candidate and a count.

  • If the current element is the same as the candidate, we increment the count.

  • If it's different, we decrement the count.

  • If the count ever reaches zero, we select the current element as a new candidate and reset the count to 1.

  • Because the majority element appears more than ⌊n/2⌋ times, its count will never be zero when the last element is processed, guaranteeing it survives.

Code (JavaScript):

Code snippet

  /**
  * @param {number[]} nums
  * @return {number}
  */
  var majorityElement = function(nums) {

      const max = {
          element : null,
          count : 0
      }

      for(let i = 0; i < nums.length; i++){
          const num = nums[i]
          if(max.count == 0){
              max.element = num
              max.count = 1
          } else if(max.element == num){
              max.count++
          } else {
              max.count--
          }
      }

      return max.element

  };

Time Complexity = O(N)

Space Complexity = O(1)

---

4. Key Takeaways

• ✨ The Boyer-Moore Voting Algorithm is a clever and highly efficient way to find the majority element in O(1) space.

• ✨ The algorithm works because the majority element's count is high enough that it will always "outlast" the combined count of all other elements.

• ✨ A simple mental model for this algorithm is to think of minority elements and majority elements fighting each other, with the majority element always surviving.

• ✨ For a simple visualization, imagine the array with the majority elements grouped at the end. Notice how the minority elements are canceled out before reaching the majority elements.