Majority Element

Problem

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.

Case 1

Input: nums = [3,2,3]
Output: 3

Case 2

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

Constraints

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

Solution

function majorityElement(nums: number[]): number {
  const countMap: Record<number, number> = {}; // Create a hash map to store counts
  for (let num of nums) {
    if (!countMap[num]) countMap[num] = 0;
    countMap[num]++;
    // Check if the current number has become the majority element
    if (countMap[num] > nums.length / 2) return num;
  }
}

Counting: Iterate through each element in the array, counting occurrences using a hash map.

Immediate Return: As soon as an element’s count exceeds n / 2, it is returned as the majority element.

Assumption Validation: The problem statement guarantees the existence of a majority element, allowing for this early return logic without needing to iterate through the entire array or map.

Complexity: The time complexity is O(n) due to a single pass through the array, and the space complexity is O(n) for storing the counts, although in practice, it’s often much less than n due to early termination.