First Missing Positive

HardAcc. 42.1%
+100 XP 50

Expert Optimization

Find the smallest missing number in O(n) time and O(1) space.

The Assignment

Your function receives nums.

  1. Cycle Sort: Move each number x to its correct index x-1 (if x is between 1 and N).
  2. After the sort, iterate again and find the first index where nums[i] !== i+1.
  3. Print i+1.

01EXAMPLE 1

Input[3, 4, -1, 1]
Output2

Explanation: 1 is there, 2 is missing.

Constraints

  • Strict O(n) time.
  • Strict O(1) space.
ArraysAlgorithms
JavaScript
Loading...
1 Hidden

Input Arguments

nums[3,4,-1,1]

Expected Output

2

Click RUN to test your solution