Majority Element

(#169), Easy

Category: Array, Hash Table, Sorting

Problem Statement

Given an array nums of size n, return the majority element. 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.

Examples

Input: nums = [3, 2, 3]

Output: 3

Explanation: 3 appears 2 times in an array of length 3, which is more than ⌊3 / 2⌋ = 1.

Input: nums = [2, 2, 1, 1, 1, 2, 2]

Output: 2

Explanation: 2 appears 4 times in an array of length 7, which is more than ⌊7 / 2⌋ = 3.

Approach

Sorting Approach

  • Sort the array in ascending order.
  • Return the element at the middle index `Math.floor(n / 2)`.
  • This works because the majority element must occupy the center position.
var majorityElement = function(nums) {
  nums.sort((a, b) => a - b);
  return nums[Math.floor(nums.length / 2)];
};

Hash Map Approach

  • Create a Hash Map to count the frequency of each element.
  • Loop through the array and update the count for each number.
  • If any element’s count becomes greater than ⌊n / 2⌋, return that element.
var majorityElement = function(nums) {
  const map = new Map();
  for (let num of nums) {
    map.set(num, (map.get(num) || 0) + 1);
    if (map.get(num) > Math.floor(nums.length / 2)) {
      return num;
    }
  }
};

Boyer-Moore Voting Algorithm

  • Initialize `count = 0` and `major = null`.
  • Loop through each number in the array:
  • - If `count == 0`, set `major = current number`.
  • - If `current number == major`, increment count, else decrement count.
  • After the loop, return `major` as the majority element.
var majorityElement = function(nums) {
  let count = 0;
  let major = null;
  for (let num of nums) {
    if (count === 0) major = num;
    count += num === major ? 1 : -1;
  }
  return major;
};

Complexity

Time: Sorting: O(n log n), Hash Map: O(n), Boyer-Moore: O(n)

Space: Sorting: O(1), Hash Map: O(n), Boyer-Moore: O(1)

Watch Explanation

📊 Presentation (PPT)

📥 Download PPT

📎 Resources