0169. Majority Element.md

Array

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      map.set(nums[i], map.get(nums[i]) + 1);
    } else {
      map.set(nums[i], 1);
    }
  }

  for (let [key, value] of map) {
    // return the key of the max value in the map
    if (value === Math.max(...map.values())) {
      return key;
    }
  }
};

Boyer-Moore Voting Algorithm

T.C O(n)
S.C O(1)

The Boyer-Moore Voting Algorithm is a linear-time algorithm for finding the majority element in an array. A majority element in an array is an element that appears more than n/2 times, where n is the length of the array.

The Boyer-Moore Voting Algorithm works by maintaining a counter that counts the number of occurrences of a particular element. When the counter reaches zero, it is reset to 1 and a new element is selected as the potential majority element. If the counter does not reach zero, it is incremented by 1 for each occurrence of the current potential majority element.

The algorithm works as follows:

Initialize a counter to 0 and a potential majority element to null. Iterate through the array, keeping track of the current element being processed (x). If the counter is 0, set the potential majority element to x and increment the counter. If the counter is not 0, increment the counter if x is equal to the potential majority element, or decrement the counter if x is not equal to the potential majority element. After the iteration is complete, the potential majority element is returned if it is indeed the majority element. Otherwise, the algorithm returns that there is no majority element. The Boyer-Moore Voting Algorithm has a time complexity of O(n) and a space complexity of O(1), making it an efficient algorithm for finding the majority element in an array.

It's worth noting that the Boyer-Moore Voting Algorithm assumes that the majority element exists. If there is no majority element, the algorithm may still return an element, but it will not be the true majority element.

var majorityElement = function(nums) {
    let count = 0, candidate = 0
    for (let num of nums) {
        if (count == 0) {
            candidate = num
        }
        count += num == candidate ? 1 : -1
    }
    return candidate
};