PROBLEM DESCRIPTION
Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
//replace all -ve numbers and 0 with a number which cannot be the answer, like N+2
for(int i=0; i<n; i++){
if(nums[i] <= 0) nums[i] = n+2;
}
//mark the numbers which are present by making the corresponding index negative
//For example, if nums[i] is 5, then make number at index 4 negative
for(int i=0; i<n; i++){
//important to take the absolute here, because we might have change this value to negative before
int currentNum = Math.abs(nums[i]);
//if the answer is in range, change the required index to negative
if(currentNum >= 1 && currentNum <= n){
nums[currentNum-1] = -1 * Math.abs(nums[currentNum-1]);
}
}
//check first non-negative index which will be our answer if anything is missing
for(int i=0; i<n; i++){
if(nums[i] > 0){
return i+1;
}
}
//otherwise, return N+1
//Example: [1, 2, 3, 4] => First missing = n+1 = 5
return n+1;
}
}