Description:
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
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: The numbers in the range [1,2] are all in the array.
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.Solution in Python:
Here is the corrected version of the text with mistakes fixed:
To solve this problem efficiently in O(n) time and O(1) auxiliary space, we can use a technique that involves rearranging the array in-place to use the array indices as a hash table. The idea is to place each positive integer ( x ) (where ( 1 ≤x ≤ n ) at the index ( x – 1 ). After rearranging, the first index ( i ) that does not contain ( i + 1 ) gives us the smallest missing positive integer.
class Solution:
def firstMissingPositive(self, nums):
n = len(nums)
# Step 1: Place each number in its correct place if possible
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
# Swap nums[i] with nums[nums[i] - 1]
correct_index = nums[i] - 1
nums[i], nums[correct_index] = nums[correct_index], nums[i]
# Step 2: Find the first index which does not have the correct number
for i in range(n):
if nums[i] != i + 1:
return i + 1
# If all indices are correct, then the missing number is n + 1
return n + 1
Explanation of the Code:
- Rearranging the Array:
We iterate through each element in the array.
For each element, we place it in its correct position (i.e., for a number x, we place it at index x−1) if it is in the range [1,n] and not already in the correct position. This is done using a while loop to handle the case where multiple swaps are needed.
This rearrangement ensures that if a number xxx is in the array and 1≤x≤n1, it will be placed at the correct index x−1.
2. Finding the Missing Positive Integer:
After rearranging the array, we iterate through the array again.
The first index iii where the value is not i+1 indicates that i+1 is the smallest missing positive integer.
If all values are in their correct positions (i.e., nums[i]==i+1 for all i), then the smallest missing positive integer is n+1.
This approach ensures that we only use O(1) additional space since all operations are performed in-place on the array, and it runs in O(n) time due to the linear scans and swaps.
Solution in Javascript:
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
const n = nums.length;
// Step 1: Place each number in its correct place if possible
for (let i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
// Swap nums[i] with nums[nums[i] - 1]
let correctIndex = nums[i] - 1;
[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
}
}
// Step 2: Find the first index which does not have the correct number
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) {
return i + 1;
}
}
// If all indices are correct, then the missing number is n + 1
return n + 1;
};Solution in Java:
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Step 1: Place each number in its correct place if possible
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// Swap nums[i] with nums[nums[i] - 1]
int correctIndex = nums[i] - 1;
int temp = nums[i];
nums[i] = nums[correctIndex];
nums[correctIndex] = temp;
}
}
// Step 2: Find the first index which does not have the correct number
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// If all indices are correct, then the missing number is n + 1
return n + 1;
}
}Solution in C#:
public class Solution {
public int FirstMissingPositive(int[] nums) {
int n = nums.Length;
// Step 1: Place each number in its correct place if possible
for (int i = 0; i < n; i++) {
// Use a while loop to keep swapping until the current number is in the correct place
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// Swap nums[i] with nums[nums[i] - 1]
int correctIndex = nums[i] - 1;
int temp = nums[i];
nums[i] = nums[correctIndex];
nums[correctIndex] = temp;
}
}
// Step 2: Find the first index which does not have the correct number
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// If all indices are correct, then the missing number is n + 1
return n + 1;
}
}