First Missing Positive

LeetCode 41 • Hard • Arrays

Input: nums = [3,4,-1,1] → Output: 2. Place each num in nums[num-1] via swap. Scan for first i where nums[i]!=i+1.

TimeO(n)

SpaceO(1)

i: — nums: []

Current i

Swap target

i—

nums[]

Speed:

Ready

Press Play. Place each num in nums[num-1] via swap. Skip if num not in [1,n]. Scan for first i where nums[i]!=i+1.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Swap nums[i] to nums[nums[i]-1] until placed. Scan for first mismatch.

═══ FIRST MISSING POSITIVE — CYCLE SORT ═══

PATTERN ▸ Index as hash (swap to correct slot) O(n) · O(1)

① FOR i IN RANGE(n)

while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:

swap nums[i], nums[nums[i]-1]

② SCAN

for i in range(n): if nums[i] != i+1: return i+1

③ RETURN

return n+1

your implementation

Verify: