Smallest Absent Positive

Hard

You are given an unsorted integer array values. Find the smallest positive integer that does not occur in it. The array may contain negative numbers, zeros and duplicates. Try to solve it in O(n) time with O(1) extra memory; you may modify the array.

Example 1

values=[5, -2, 1, 3, 2] → 4

1, 2 and 3 are all present, but 4 is not.

Example 2

values=[0, -7] → 1

There are no positive numbers at all, so the answer is 1.

Example 3

values=[2, 1, 3] → 4

Every number from 1 to 3 is there, so the first one missing is 4.

Constraints

1 ≤ len(values) ≤ 10⁵
-2³¹ ≤ values[i] ≤ 2³¹ - 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table

Similar problems

Complete the Sudoku Hard Every Way to Space the Words Hard Stars on One Straight Line Hard Islands After Each Landfill Hard Glued Into a Palindrome Hard

Input

values=[5, -2, 1, 3, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 128 tests on the server, hidden ones included.