39. First Missing Positive

HardArray

Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Examples

Example 1

Input: nums = [1,2,0]

Output: 3

Explanation: 1 and 2 are both present, and 3 is not, so the smallest missing positive is 3.

Example 2

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

Output: 2

Explanation: 1 is present, but 2 is not. The negative number -1 is ignored.

Example 3

Input: nums = [7,8,9,11,12]

Output: 1

Explanation: The smallest positive integer, 1, does not appear, so the answer is 1.

Constraints

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

Hints

How to solve First Missing Positive: approach and complexity

Cyclic Sort (Index as Hash): O(n) time, O(1) space.

Place each number i at index i-1. Then scan for the first index where nums[i] != i+1.

Watch it run step by step