Given an unsorted integer array nums
, return the smallest missing positive integer.
O(n)
O(1)
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Input: nums = [-1,7,8,9,11,12,-10]
Output: 1
Explanation: The smallest positive integer 1 is missing.
The first thing that comes to mind is to do brute force. The idea is simple; sort through all positive numbers from 1 until we find the first missing one.
Complexity:
O(n*n)
O(1)
public int firstMissingPositive(int[] nums) {
int positiveNumber = 1;
while (true) {
boolean exists = false;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == positiveNumber) {
exists = true;
break;
}
}
if (!exists) return positiveNumber;
positiveNumber++;
}
}
The problem is that for each number, we re-pass through the entire array. Let's try to reduce the number of iterations by allocating extra memory.
We can use a HashMap
or a boolean array
of size N to remember which elements are in the array. And then, by simple enumeration, find the minimum positive element.
Complexity:
O(n)
O(n)
public int firstMissingPositive(int[] nums) {
Map<Integer, Boolean> map = new HashMap<>();
for (int n: nums) {
if (n > 0) {
map.put(n, true);
}
}
int number = 1;
while(true) {
if (map.get(number) == null) {
return number;
}
number++;
}
}
In the first loop on lines 3-7, we remember only positive numbers, since we will need to work with them further.
In the second loop on lines 9-13, we sequentially check the numbers starting from 1. If the number is on the map, then we move on, otherwise, return it.
Whenever we know how to solve an array problem using a HashMap but extra space is not allowed, try using the array itself as a HashMap.
To use the original array as a HashMap, we need to take a closer look at the problem statement. In the worst case, the array will contain all positive numbers from 1 to N (the length of the array), and then the answer will be N+1.
Complexity:
O(n)
O(1)
public int firstMissingPositive(int[] nums) {
int n = nums.length;
int fakeNumber = n + 1;
// Step 1.
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = fakeNumber;
}
}
// Step 2.
for (int i = 0; i < n; i++) {
int num = Math.abs(nums[i]); // point 1
if (num == fakeNumber) { // point 2
continue;
}
num--; // point 3
if (nums[num] > 0) {
nums[num] *= -1;
}
}
// Step 3.
for (int i = 0; i < n; i++) {
if (nums[i] >= 0) {
return i + 1;
}
}
// otherwise return n+1
return n + 1;
}
I would like to draw your attention to a few major points:
Since we mark cells with negation, we must ignore the sign when extracting.
In step 1, we changed all the numbers to ignore fakeNumber, so don't forget to ignore them.
Do not forget to decrease the value by 1; since, in java, indexing starts from zero (so the number 1 will be at pos 0).
The algorithm listed above gives us the following result.
I hope this article helped you understand how to solve this type of problem. I will be glad for your feedback.
See you soon! ✌