First Missing Positive
Given an unsorted integer array nums, return the smallest missing positive integer. Must run in O(n) time and O(1) auxiliary space.

30:00

First Missing Positive
hard
Topics
Companies

Given an unsorted integer array nums, return the smallest missing positive integer. Must run in O(n) time and O(1) auxiliary space.

Example 1:
Input: [3,4,-1,1]
Output: 2
Constraints:

  • 1≤nums.length≤1051 \leq \text{nums.length} \leq 10^5

  • −231≤nums[i]≤231−1-2^{31} \leq \text{nums}[i] \leq 2^{31} - 1

Input
arr =[3,4,-1,1]
Phase 1: Cyclic Sort
nums (value at index i should be i+1)[1]3i=0[2]4i=1[3]-1i=2[4]1i=3
Current Index
Target Index
Swapping
Correctly Placed
Variables
VariableValue
n4
DepthFunction Call
1firstMissingPositive(nums=[3, 4, -1, 1])
0/21