LeetCode 169. Majority Element (javascript)

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.

Example 1:

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

Example 2:

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

Constraints:

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

Solution 1: (Hash Table)

• Time Complexity : O(n)
• Space Complexity : O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let map = new Map();
    for (let num of nums) {
        map.set(num, (map.has(num) ? map.get(num) : 0)  + 1);
        if (map.get(num) > nums.length / 2) return num;
    }
    return -1;
};

Solution 2: (Sorting)

• Time Complexity : O(n)
• Space Complexity : O(1)

var majorityElement = function(nums) {
    nums.sort();
    return nums[Math.floor(nums.length / 2)];
};

Solution 3: (Divide and conquer)

• Time Complexity : O(nlogn)
• Space Complexity : O(logn)

var majorityElement = function(nums) {
    return majority(nums, 0, nums.length - 1);
};

function majority(nums, l, r) {
    if (l === r) return nums[l];
    const mid = l + Math.floor((r - l) / 2);
    const left = majority(nums, l , mid);
    const right = majority(nums, mid + 1, r);
    if (left === right) return left;
    return nums.slice(l, r + 1).filter(x => x === left).length >
           nums.slice(l, r + 1).filter(x => x === right).length
           ? left : right;
}