InternDoor

Smallest positive left out

Hardarrays · hashing · in-place

Reported in interviews at (where)

Given an unsorted list of whole numbers nums (any of them may be negative, zero or repeated), return the smallest positive whole number (1, 2, 3, ...) that does not appear in it.

The real test is doing it in O(n) time with only O(1) extra space: you may rearrange nums itself.

Example 1
Input
nums = [7,8,9]
Output
1

1 is not there.

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

1 and 2 are there, 3 is not.

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

Negatives and repeats change nothing: 1, 2 and 3 are there.

Limits

  • 1 <= nums.length <= 100000
  • -2^31 <= nums[i] <= 2^31 - 1

Hints

Hint 1

The answer is at most n + 1.

Hint 2

Put each value v from 1 to n at position v - 1 by swapping, then find the first position that holds the wrong value.

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.