Majority Element

EasyArray Hash Table Sorting

A spacecraft carries many redundant sensors that measure the same quantity. A faulty sensor can report any value, but more than half of the sensors are healthy, and every healthy sensor reports exactly the same integer. nums[i] is the reading from sensor i.

Return the reading shared by the healthy sensors: the value that fills strictly more than n / 2 of the n positions. Every test contains such a value.

Example 1

Input: nums = [-40,12,-40,-40,7]
Output: -40

Explanation: Three of the five sensors agree on -40.

Example 2

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

Explanation: 6 appears 4 times out of 7, which is more than 7 / 2 = 3.5.

Example 3

Input: nums = [13]
Output: 13

Explanation: A single sensor is trivially a majority.

Constraints

nums holds between 1 and 50,000 readings.
Each reading lies between -10^9 and 10^9.
One value always fills more than half of nums.

Follow-up: The flight computer has almost no spare memory. Can you find the shared reading in one pass while storing only a couple of variables?

💡 Hint 1

Counting occurrences in a hash map is O(n) time but O(n) space. Sorting also works: which index must the majority element occupy after sorting?

💡 Hint 2

For O(1) space, pair up each occurrence of the majority value with a different value and cancel them out. Since it fills more than half the array, something of it survives.

💡 Hint 3

Keep a candidate and a count: when count is 0, adopt the current value; add 1 when you see the candidate and subtract 1 otherwise.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use the Boyer-Moore voting idea. Keep a candidate and a count. When count is 0, the current value becomes the candidate. Each occurrence of the candidate adds a vote and every other value removes one. Every removal cancels one majority occurrence against one non-majority occurrence at most, and the majority value has more occurrences than all other values combined, so it is the candidate left standing at the end.

Time O(n)Space O(1)

function majorityElement(nums) {
  let candidate = 0;
  let count = 0;
  for (const x of nums) {
    if (count === 0) candidate = x;
    count += x === candidate ? 1 : -1;
  }
  return candidate;
}

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x;
            count += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit