Majority element (Boyer–Moore)

Easy TimeO(n) SpaceO(1)

Given an array nums in which one value appears more than half the time, return that value. The array is unsorted, a majority value is guaranteed to exist, and it is the value itself that comes back rather than where it sits.

Examples

Example 1

Input
nums = [2, 2, 1, 3, 2, 2]
Output
2
Four 2s out of six, with a 1 and a 3 between them — each cancels one 2 and the majority still survives.

Example 2

Input
nums = [6, 6, 7, 6, 7]
Output
6
Three 6s out of five: the two 7s cancel two of them, and one is still standing.

The Code

function majorityElement(nums) {
  let candidate = null;
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (count === 0) {
      candidate = nums[i];
      count = 1;
    } else if (nums[i] === candidate) {
      count++;
    } else {
      count--;
    }
  }
  return candidate;
}
majorityElement([2, 2, 1, 3, 2, 2]);
Done
Step through majorityElement([2, 2, 1, 3, 2, 2]) call by call

Explanation

Pair each value off against a different one, and both drop out. A value appearing more than half the time cannot be paired away, because there are not enough other values to cancel it — so whatever is left unpaired at the end is that value. candidate is what is currently unpaired and count is how many copies of it are waiting to be cancelled; when count falls to zero everything seen so far has paired off exactly, and what remains of the array is the same problem in miniature.

  1. 1

    Nothing is unpaired yet — count is 0 — so the value at i becomes the candidate: one 2, waiting to be cancelled.

    i
    2
    0
    2
    1
    1
    2
    3
    3
    2
    4
    2
    5

    candidate=nonecount=0

    candidate = 2 · count = 1

  2. 2

    nums[1] is another 2, which agrees with the candidate, so now two 2s are unpaired.

    2
    0
    i
    2
    1
    1
    2
    3
    3
    2
    4
    2
    5

    candidate=2count=1

    count → 2

  3. 3

    nums[2] is a 1. It pairs off against one of those 2s and both drop out of the reckoning — which is why it never matters what the disagreeing value is, only that it disagrees.

    2
    0
    2
    1
    i
    1
    2
    3
    3
    2
    4
    2
    5

    candidate=2count=2

    count → 1

  4. 4

    nums[3] is a 3 and pairs off the last unpaired 2. count is 0, so the first four values have cancelled each other exactly — two 2s against a 1 and a 3 — and can be forgotten.

    2
    0
    2
    1
    1
    2
    i
    3
    3
    2
    4
    2
    5

    candidate=2count=1

    count → 0

  5. 5

    What is left is the same problem on a shorter array, so it starts again: with nothing unpaired, the value at i becomes the candidate.

    2
    0
    2
    1
    1
    2
    3
    3
    i
    2
    4
    2
    5

    candidate=2count=0

    candidate = 2 · count = 1

  6. 6

    The last value is another 2, so the run ends with two unpaired 2s and candidate is returned. Four 2s against one 1 and one 3 — not enough of them to pair the 2s away, which is exactly what “more than half” guarantees.

    2
    0
    2
    1
    1
    2
    3
    3
    2
    4
    i
    2
    5

    candidate=2count=1

    count → 2 · return 2

More like this

All arrays & loops examples (10) →