1. Problem Statement (Simple Explanation):
You’re given an unsorted integer array nums.
You must return the smallest positive integer (i.e., >= 1) that is not present in nums.
Constraints:
Must run in O(n) time.
Must use O(1) auxiliary space (i.e., in-place; ignoring input array itself).
2. Examples:
Example 1:
Input: nums = [1,2,0]
Present positives: 1, 2.
Missing smallest positive: 3.
Output: 3
Example 2:
Input: nums = [3,4,-1,1]
Present positives: 1, 3, 4.
Smallest missing positive is 2.
Output: 2
Example 3:
Input: nums = [7,8,9,11,12]
No 1 in the array, so the smallest missing positive is 1.
Output: 1
3. Key Insight:
For an array of length n:
The smallest missing positive integer is always in the range: [1, n+1]
Because:
In the best case, the array contains all 1..n, so the answer is n+1.
Otherwise, some number in 1..n is missing.
We can use the array itself as a hash map to record which numbers in [1..n] are present, in O(1) extra space.
4. Approach – In-place Index Mapping (Cyclic Placement):
We will rearrange numbers so that:
If possible, nums[i] == i + 1 for 0 <= i < n.
Meaning:
Place value 1 at index 0
value 2 at index 1
...
value k at index k-1
After this arrangement, we can scan once:
The first index i where nums[i] != i + 1 means i + 1 is missing.
If all positions match, then the missing value is n + 1.
Step-by-Step:
Let n = nums.length.
Rearrange in place:
For each index i from 0 to n - 1:
While nums[i] is in the range [1..n] and nums[nums[i] - 1] != nums[i]:
Swap nums[i] and nums[nums[i] - 1].
We do not increment i here; we re-check the new nums[i].
This loop will:
Move each number x into its correct position x-1 if possible.
Skip:
Negative numbers
Zero
Numbers > n
Duplicates (since we check nums[nums[i]-1] != nums[i]).
Scan to find missing positive:
For i from 0 to n - 1:
If nums[i] != i + 1, then return i + 1.
If no such i is found, return n + 1.
Example Walkthrough – [3,4,-1,1]:
n = 4
Initial: [3,4,-1,1]
i = 0:
nums[0] = 3 ∈ [1..4], target index = 3-1=2
nums[2] = -1 != 3 → swap nums[0] and nums[2]
Array → [-1,4,3,1]
Now nums[0] = -1 (out of range) → move to i = 1.
i = 1:
nums[1] = 4, target index = 4-1=3
nums[3] = 1 != 4 → swap
Array → [-1,1,3,4]
Now nums[1] = 1, target index = 0
nums[0] = -1 != 1 → swap nums[1] and nums[0]
Array → [1,-1,3,4]
Now nums[1] = -1 → out of range → i = 2.
i = 2: nums[2] = 3 at index 2 → correct (3-1=2).
i = 3: nums[3] = 4 at index 3 → correct (4-1=3).
Now array: [1,-1,3,4]
Scan:
i=0: nums[0]=1 -> ok
i=1: nums[1]=-1 != 2 → return 2.
Pseudo-code:
Time: We might swap each element a few times, but each element can be moved at most once to its correct position. Overall: O(n)
Space: We only use a few variables, no extra arrays: O(1)
5. Java code:
6. C code:
8. Python code:
9. JavaScript code:
Comments
Post a Comment