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.

 

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    const map = {};
    for (const n of nums) {
        if (!(n in map)) {
            map[n] = 0;
        }
        map[n]++;
        if (map[n] > nums.length / 2) {
            return n;
        }
    }
};

Use hashmap map to keep track of how many times a value in nums has appeared before, and check if an element has appears a majority number of times. Another method is to sort nums in place and return the centre element.

Follow-up

Could you solve the problem in linear time and in O(1) space?

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let candidate = null;
    let counter = 0;
    for (const n of nums) {
        if (!counter) {
            candidate = n;
        }
        counter += candidate === n ? 1 : -1;
    }
    return candidate;
};

We will implement the Boyer-Moore majority vote algorithm. Essentially, when counter = 0, we choose a candidate value (ie. the element at the index of the current iteration). Next, we increment counter if we encounter a value not equal to candidate, and decrement counter if we encounter a value equal to candidate (for as long as counter != 0).

Thus, when counter = 0, it must hold that the number of values that we passed by which are equal to candidate is the same as the number of values not equal to candidate.

We repeat this procedure until all elements in nums are accounted for. Since there is a value that appears a majority number of times (ie. more than half), it is impossible to match it one-to-one against the rest of the elements in nums, and so the last candidate (which is guaranteed not to be matched) must be the value we're looking for.

For example, let nums = [2, 2, 3, 3, 3, 2, 2, 2, 3]. The array can be visualized as being split into [2, 2, 3, 3 | 3, 2 | 2, 2, 3], where the first element of each split is candidate, and the last candidate is the majority value.