Smallest Missing Positive Integer in Linear Time and Constant Extra Space
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given an unsorted list of integers `nums`, which may contain negative numbers, zeros, duplicates, and values far larger than the length of the list. Return the smallest positive integer, that is the smallest integer that is at least `1`, that does not appear in `nums`.
In the interview, a first solution that ran in linear time but used extra memory proportional to the input was accepted as a starting point, and the interviewer then asked for the same result using only constant extra space. Aim for that tighter target.
### Function Signature
```python
def first_missing_positive(nums: list[int]) -> int:
```
### Rules
- Target complexity: `O(n)` time and `O(1)` auxiliary space, where `n = len(nums)`. The list may be rearranged or overwritten in place; its contents after the call do not matter.
- Return only the missing value.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-2147483648 <= nums[i] <= 2147483647`
- The answer is a positive integer that fits in a signed 32-bit integer.
### Examples
**Example 1**
- Input: `nums = [4, -2, 1, 2]`
- Output: `3`
- Explanation: `1` and `2` are present and `3` is not.
**Example 2**
- Input: `nums = [5, 6, 100, -3]`
- Output: `1`
- Explanation: `1` does not appear, so it is the answer, however large the other values are.
**Example 3**
- Input: `nums = [1, 2, 2, 3]`
- Output: `4`
- Explanation: `1`, `2` and `3` all appear (`2` twice), so the smallest missing positive integer is `4`.
Overview: Find the smallest positive integer missing from an unsorted list that may contain negatives, zeros, duplicates and very large values. Tests careful edge-case handling and meeting a linear-time, constant-extra-space target on inputs of up to 100,000 elements.
Read the full Google Software Engineer interview experience this question came from
You are given an unsorted list of integers `nums`. It may contain negative numbers, zeros, duplicates, and values far larger than the length of the list. Return the smallest positive integer (the smallest integer that is at least `1`) that does not appear in `nums`.
A linear-time solution that uses extra memory proportional to the input is a fine starting point, but aim for the tighter target: `O(n)` time and `O(1)` auxiliary space, where `n = len(nums)`. You may rearrange or overwrite `nums` in place; its contents after the call do not matter. Return only the missing value.
Because this value is unique for every input, there is exactly one correct answer; it always lies in `[1, n + 1]`.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-2147483648 <= nums[i] <= 2147483647` (every value fits in a signed 32-bit integer)
- The answer is a positive integer that fits in a signed 32-bit integer.
### Example 1
- Input: `nums = [4, -2, 1, 2]`
- Output: `3`
- Explanation: `1` and `2` are present and `3` is not.
### Example 2
- Input: `nums = [5, 6, 100, -3]`
- Output: `1`
- Explanation: `1` does not appear, so it is the answer, however large the other values are.
### Example 3
- Input: `nums = [1, 2, 2, 3]`
- Output: `4`
- Explanation: `1`, `2` and `3` all appear (`2` twice), so the smallest missing positive integer is `4`.
Constraints
- 1 <= len(nums) <= 10^5
- -2147483648 <= nums[i] <= 2147483647
- The answer is a positive integer that fits in a signed 32-bit integer
Examples
Input: ([4, -2, 1, 2],)
Expected Output: 3
Input: ([5, 6, 100, -3],)
Expected Output: 1
Hints
- For a list of length n, the answer can only be one of 1, 2, ..., n + 1. Values outside [1, n] can never affect it.
- You are allowed to overwrite the input. Could the list itself serve as the record of which values in [1, n] you have seen?
- Try to move every value v in [1, n] to a fixed home position determined by v, then scan for the first position that does not hold its expected value. Watch out for duplicates causing endless swaps.
Community answers
Answer by Coderka14
Same as : https://leetcode.com/problems/first-missing-positive
class Solution {
public:
int firstMissingPositive(vector& a) {
int n = a.size();
int cnt=0;
// number is in range 1 to n;
for(int i=0;i0 and a[i]<=n and a[a[i]-1]!=a[i])
swap(a[i],a[a[i]-1]);
}
for(int i=0;i
using namespace std;
class Solution {
public:
int firstMissingPositive(vector& nums) {
unordered_set st;
for (int x : nums)
st.insert(x);
for (int x = 1; x <= nums.size() + 1; x++) {
if (!st.count(x))
return x;
}
return -1;
}
};