First Missing Positive

Big-O & the Python Toolkit, problem 7 of 7

First Missing Positive

Hard

LC #41

arraycyclic sortin-place

Not attempted yet

Given an unsorted list of integers nums, return the smallest positive integer that does not appear in it.

Aim for O(n) time and O(1) extra space. (You may rearrange nums.)

Example 1

Input: nums = [2, 1, 0]
Output: 3

Example 2

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

Example 3

Input: nums = [9, 8, 10]
Output: 1

Constraints

  • 0 ≤ nums.length ≤ 10⁵
  • -2³¹ ≤ nums[i] ≤ 2³¹ − 1

Python

Loading draft…

Test results

10 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 7 hidden

Run examples, then submit all tests.