The value that fills more than half
nums holds n whole numbers, and one value appears more than n / 2 times. Return that value.
Counting every value with a map works. Can you do it with O(1) extra memory?
- Input
nums = [3,1,3,3,2]- Output
3
3 appears 3 times out of 5, which is more than half.
- Input
nums = [-7,4,-7,-7]- Output
-7
Negative values count the same way: -7 fills 3 of the 4 places.
- Input
nums = [9]- Output
9
A single value is more than half of an array of one.
Limits
1 <= nums.length <= 100000-1000000000 <= nums[i] <= 1000000000one value appears more than nums.length / 2 times
Hints
Hint 1
Keep one candidate and a count. A matching value adds 1, any other value takes 1 away.
Hint 2
When the count falls to 0, the next value becomes the candidate. Pairs of different values cancel out, and the majority can never be cancelled completely.
Where this was reported
- Amazon, SDE intern interview, 2026 (Medium)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
