LeetCode - First Missing Positive
Problem description
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
1
2
Input: [1,2,0]
Output: 3
Example 2:
1
2
Input: [3,4,-1,1]
Output: 2
Example 3:
1
2
Input: [7,8,9,11,12]
Output: 1
Note:
- Your algorithm should run in O(n) time and uses constant extra space.
Analysis
Basic idea is to use value as index, and make positive value to become negative to indicate that this value of index exists.
Here’s the code:
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Base case.
int contains = 0;
for (int i = 0; i < n; i++)
if (nums[i] == 1) {
contains++;
break;
}
if (contains == 0)
return 1;
// nums = [1]
if (n == 1)
return 2;
// Replace negative numbers, zeros,
// and numbers larger than n by 1s.
// After this convertion nums will contain
// only positive numbers.
for (int i = 0; i < n; i++)
if ((nums[i] <= 0) || (nums[i] > n))
nums[i] = 1;
// Use index as a hash key and number sign as a presence detector.
// For example, if nums[1] is negative that means that number `1`
// is present in the array.
// If nums[2] is positive - number 2 is missing.
for (int i = 0; i < n; i++) {
int a = Math.abs(nums[i]);
// If you meet number a in the array - change the sign of a-th element.
// Be careful with duplicates : do it only once.
if (a == n)
nums[0] = - Math.abs(nums[0]);
else
nums[a] = - Math.abs(nums[a]);
}
// Now the index of the first positive number
// is equal to first missing positive.
for (int i = 1; i < n; i++) {
if (nums[i] > 0)
return i;
}
if (nums[0] > 0)
return n;
return n + 1;
}
}
What to improve
- use value as index