InternDoor

The value that fills more than half

Easyarrays · counting · voting

Reported in interviews at (where)

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?

Example 1
Input
nums = [3,1,3,3,2]
Output
3

3 appears 3 times out of 5, which is more than half.

Example 2
Input
nums = [-7,4,-7,-7]
Output
-7

Negative values count the same way: -7 fills 3 of the 4 places.

Example 3
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] <= 1000000000
  • one 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

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.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.