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)$