169. Majority Element

Solution (HashMap)

/**
 * @param {number[]} nums
 * @return {number}
 */
 var majorityElement = function(nums) {
    const map = [];
    
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];
        if (map[num] >= 0) {
            map[num]++;
        } else {
            map[num] = 1;
        }
        
        if (map[num] > (nums.length / 2 | 0)) {
            return num;
        }
    }
    
    return 0;
};

Complexity

  • Time Complexity: O(N), because we iterate over nums.
  • Space Complexity: O(N), where N is at most n-n/2.

Solution (Sorting)

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    nums = nums.sort();
    return nums[nums.length / 2 | 0];
};

Complexity

  • Time Complexity: O(NlogN), because of the sorting.
  • Space Complexity: O(1), if we sort the array in place or O(N) if we sort a copy.

All Solutions