41. First Missing Positive

Hard

14.1K

1.6K

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 constant extra space.

**Example 1:**

Input:nums = [1,2,0]Output:3Explanation:The numbers in the range [1,2] are all in the array.

**Example 2:**

Input:nums = [3,4,-1,1]Output:2Explanation:1 is in the array but 2 is missing.

**Example 3:**

Input:nums = [7,8,9,11,12]Output:1Explanation:The smallest positive integer 1 is missing.

**Constraints:**

`1 <= nums.length <= 10`

^{5}`-2`

^{31}<= nums[i] <= 2^{31}- 1

Accepted

889.7K

Submissions

2.4M

Acceptance Rate

36.9%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved