Majority Element

Easy#169counting

You get an array in which one value fills more than half of the places. Find that value. Our example: [3, 1, 3, 2, 3, 3, 1] — the answer is 3, it appears 4 times out of 7.

169 Majority ElementWalkthrough · 1×

Example: [3, 1, 3, 2, 3, 3, 1]: 7 numbers, so the answer appears more than 3.5 times. Below is the map: value and its count.

03112332435361count—
not reached yetcurrent numbercountedthe majority

Start with an empty map: every value counts 0

01/20
restart · back · play · step
Speed
1function majorityElement(nums):
2 count = empty map // missing keys: 0
3 for each x in nums:
4 count[x] = count[x] + 1
5 if count[x] > len(nums) / 2:
6 return x
state
count
{}
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Count each value as you go: the map holds value → how many times so far, and finds the count at once.
  2. The answer appears more than n / 2 times, and then no other value can: together they would not fit in the array. So the first count that goes over n / 2 is the answer.
  3. That is why the run may stop right there: the numbers after it cannot change the answer.

Complexity

Time O(n): at most one pass. Memory O(n): the map may hold many different values. Boyer–Moore voting finds the answer with O(1) memory, but it is a different idea.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.