Coding Interview Questions | Majority Element

December 31st, 2023

Majority Element Problem Introduction:

This summary will talk about my solution to the majority element problem as seen on leetcode here.

How do you solve the Majority Element Problem in O(n) time?

Solution

function majorityElement(nums: number[]): number {
  if (nums.length === 1) {
    return nums[0];
  }
  const majorityElementThreshold = Math.floor(nums.length / 2);
  const numCountMap = new Map<number, number>();

  for (const num of nums) {
    const currentCount = numCountMap.get(num);

    if (!currentCount) {
      numCountMap.set(num, 1);
      continue;
    }

    if (currentCount + 1 > majorityElementThreshold) {
      return num;
    }

    numCountMap.set(num, currentCount + 1);
  }

  return -1;
}

Majority Element Solution Summary:

1. Input Validation: The solution above first starts by checking if the length of the input array nums is 1. If true, it directly returns the only element as the majority element.

2. Map Initialization: We then initialize a Map named numCountMap to keep track of the count of each unique number in the array.

3. Array Iteration: Then, we iterate through the input array nums and updates the count for each number in the numCountMap. If the count of a number reaches or exceeds the majority element threshold, the function returns that number as the majority element.

Complexities

• The time complexity of the provided solution is O(n), where n is the length of the input array. This is because it iterates through the array once.
• The space complexity is O(n) due to the numCountMap, where n is the number of unique elements in the array.

How do I solve the Majority Element Problem with O(1) space?

Bonus Solution

To solve this problem in O(1) space, we take advantage of an algorithm known as Boyer-Moore. The link I’ve provided does an excellent job of explaining why this algorithm works. Effectively, it’s a “counting vote” algorithm that tracks the current majority element along with the count of the majority element. As we loop through the element in the array, the numbers, acting as “votes” will cancel each other out until a number with the most votes “wins” once the iteration of the loop is completed.

Below you will find my solution using this algorithm.

function majorityElement(nums: number[]): number {
  let majorityElement = nums[0];
  let count = 0;

  // Traverse nums to determine majority element
  for (const num of nums) {
    if (count === 0) {
      count += 1;
      majorityElement = num;
    } else {
      if (num === majorityElement) {
        count += 1;
      } else {
        count -= 1;
      }
    }
  }

  // At this point in the algorithm, we would
  // loop through again to count the occurrences
  // of the majority element to ensure the finalCount > nums.length / 2.
  // However, the problem statement ensures that a majority element
  // exists, thus this loop is commented out.

  // let finalCount = 0
  // for(const num of nums){
  //   if(num === majorityElement){
  //     finalCount += 1
  //   }
  // }

  // return finalCount > nums.length / 2

  return majorityElement;
}