Majority Element

In this article, we explore different ways to solve this problem, ranging from the basic to the more advanced, to help you better understand how to approach similar algorithmic challenges.

Problem Statement:

Given an array nums of size n, return the majority element.

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

Approach 1: Brute Force

This approach uses two nested loops to compare each element with every other element in the array. The count of occurrences for each element is maintained, and if any element’s count exceeds half the array size, it is considered the majority element. While it provides a straightforward solution, it’s not efficient.

// ES6 Arrow Function
const majorityElement = nums => {
    const n = nums.length;

    for(let i = 0; i < n; i++) {
        let count = 0; 

        for(let j = 0; j < n; j++) {
            if(nums[i] === nums[j]) count++;
        }

        if(count > n/2) return nums[i];
    }

    return -1;
}

Time Complexity: O(N²)

Space Complexity: O(1)

Note: Brute force approach is not the most efficient solution for finding the majority element. It is included here for explanation purposes, but in practice, it is unsuitable for larger input sizes due to its quadratic time complexity.

Approach 2: Hashmap

In this approach, we iterate through the array and maintain a Hashmap to store the count of each element. We update the count for each element and check if it exceeds half the array size, indicating the majority element.

// ES6 Arrow Function
const majorityElement = nums => {
    let n = nums.length;
    let map = new Map();

    for(let i = 0; i < n; i++) {
        const num = nums[i];
        map.set(num, (map.get(num) || 0) + 1);

        if(map.get(num) > n / 2) return num;
    }

    return -1;
}

Time Complexity: O(N)

Space Complexity: O(N)

Approach 3: Boyer-Moore Voting Algorithm

The Boyer-Moore Voting Algorithm scans the array and maintains a candidate and a count. It cancels out non-majority elements and updates the candidate accordingly. The final candidate is the majority element. It is an optimized approach that achieves a time complexity of O(n) and constant space.

// ES6 Arrow Function
const majorityElement = nums => {
    let candidate = null;
    let count = 0;

    for (let i = 0; i < nums.length; i++) {
      if (count === 0) {
        candidate = nums[i];
        count++;
      } else if (nums[i] === candidate) {
        count++;
      } else {
        count--;
      }
    }

    return candidate;
}