https://leetcode.com/problems/first-missing-positive/
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
The key here is to use swapping to keep constant space and also make use of the length of the array, which means there can be at most n positive integers. So each time we encounter an valid integer, find its correct position and swap. Otherwise we continue.
class Solution {
public int firstMissingPositive(int[] nums) {
int i = 0, n = nums.length;
while (i < n) {
// If the current value is in the range of (0,length) and it's not at its correct position,
// swap it to its correct position.
// Else just continue;
if (nums[i] >= 0 && nums[i] < n && nums[nums[i]] != nums[i]) {
swap(nums, i, nums[i]);
} else {
i++;
}
}
int k = 1;
// Check from k=1 to see whether each index and value can be corresponding.
while (k < n && nums[k] == k) {
k++;
}
// If it breaks because of empty array or reaching the end. K must be the first missing number.
if (n == 0 || k < n) {
return k;
} else {
// If k is hiding at position 0, K+1 is the number.
return nums[0] == k ? k + 1 : k;
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
Complexity Analysis
- Time complexity : O(N) since all we do here is four walks along the array of length
N
. - Space complexity : O(1) since this is a constant space solution.
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
int contains = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == 1) {
contains++;
break;
}
}
if (contains == 0) {
return 1;
}
if (n == 1) {
return 2;
}
for (int i = 0; i < n; i++) {
if ((nums[i] <= 0) || (nums[i] > n)) {
nums[i] = 1;
}
}
for (int i = 0; i < n; i++) {
int a = Math.abs(nums[i]);
if (a == n) {
nums[0] = - Math.abs(nums[0]);
} else {
nums[a] = - Math.abs(nums[a]);
}
}
for (int i = 1; i < n; i++) {
if (nums[i] > 0) {
return i;
}
}
if (nums[0] > 0) {
return n;
}
return n + 1;
}
}