Reference: LeetCode
Difficulty: Hard

Problem

Given an unsorted integer array, find the smallest missing positive integer.

Example:

1
2
3
4
5
6
7
8
Input: [1,2,0]
Output: 3

Input: [3,4,-1,1]
Output: 2

Input: [7,8,9,11,12]
Output: 1

Follow up: Your algorithm should run in $O(n)$ time and uses constant extra space.

Analysis

Basic Idea: Since there are only n spaces in the array, we have the follow different cases (n = 5):

  • [1, 2, 3, 4, 5]: Return 6. (n + 1)
  • [1, 2, 2, 4, 5]: Return 3. ([1, n])
  • [1, 2, -1, 2, 5]: Return 3. ([1, n])

The invariant is that the smallest positive integer must be in the interval [1, n + 1].

Brute-Force

For each value in [1, n], check if it is in nums.

  • If it does not exist, return the corresponding index i.
  • If all values in [1, n] exist in the array, return n + 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 1; i <= n; ++i) {
boolean exist = false;
for (int j = 0; j < n; ++j) {
if (nums[j] == i) {
exist = true;
break;
}
}
if (exist == false) return i;
}
return n + 1;
}

Time: $O(N^2)$
Space: $O(1)$

Hash Set

The brute-force approach could be optimized by using a hash set.

1
2
3
4
5
6
7
8
9
10
11
12
13
public int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int val : nums) {
set.add(val);
}
int n = nums.length;
for (int i = 1; i <= n; ++i) {
if (set.contains(i) == false) {
return i;
}
}
return n + 1;
}

Time: $O(N)$
Space: $O(N)$

In-place Optimization

We can actually use the values in the array to indicate if the values from 1 to n exists.

1
2
Input: [3, 4, -1, 1]
Output: 2

For example, since 3 exists, we set the value (-1) at 3 - 1 to negative.

Before this process, we should traverse the array, setting all non-positive numbers and out-of-bound numbers to 1. In the above example, the output of preprocessing will be [3, 4, 1, 1].

Since we set those values to 1, during the first iteration, we must check if 1 exists. If it does not exist, the result is going to be 1. No further action should be made.

Then we process the array [3, 4, 1, 1], the output is [-3, 4, -1, -1]. In the final pass, we find that 4 is positive. So the element is the index of 4 plus one, which is 2.

Note: When using val as index, remember to use the absolute value because it might be set to negative in advance.

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
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// set all negative numbers and >n numbers to "1"
// meanwhile, check if there is "1"
boolean oneExist = false;
for (int i = 0; i < n; ++i) {
int val = nums[i];
if (val == 1) oneExist = true;
if (val <= 0 || val > n) nums[i] = 1;
}
if (oneExist == false) return 1;

// second pass
// 3 4 1 1 1 5 1 1 2 1
for (int i = 0; i < n; ++i) {
int val = Math.abs(nums[i]); // 1 ~ n
nums[val - 1] = -Math.abs(nums[val - 1]);
}

// third pass
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) { // it means (i + 1) is not set <=> does not exist
return i + 1;
}
}
return n + 1;
}

Time: $O(N)$
Space: $O(1)$