[LeetCode] 41. First Missing Positive

Posted on | In

Problem

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.

Explanation 1

  1. If the input array length is 3, then the result can be 4 at maximum. For example:

    1
    2
    3
    4
     input = [1, 2, 3], result == 4.
 input = [1, 5, 3], result < 4.
 input = [3, 3, 3], result < 4.
 input = [-1, 3, 2], result < 4.

  2. We can create a boolean array with length same as the input array length. Then loop through each number, if the number num is not positive or the number is greater than length, we ignore it. Else, we put the boolean array’s index num-1 to true. Finally, we loop through the boolean array and find out the first false index and plus one to it and return as the result. For example

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     input = [1, 5, 3]
 boolean = [false, false, false]
 iterate to 1:
 boolean = [true, false, false]
 iterate to 5:
 boolean = [true, false, false]
 iterate to 3:
 boolean = [true, false, true]

 return 2 as the result.

  3. If all elements in the boolean array are true, then we return array length plus one. For example input=[1, 2, 3], booleanArr = [true, true, true]. We return 4.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;
        boolean[] arr = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0 || nums[i] > nums.length) continue;
            arr[nums[i]-1] = true;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == false) return i+1;
        }
        return nums.length+1;
    }
}

Explanation 2

  1. We loop through the array, if the number is not positive, we change it to the maximum of integer.

  2. Second loop, if the current element’s value is greater than array length, we ignore it. Else, we use the current element’s value minus one as index, then in the array, change that index’s element to negative.

  3. Third loop, if the current element is positive, then we return its index plus one as the result. If finish looping and no element is positive, then we return the length plus one as result.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     input:
 [2, -1, 3, 1, 0, -5, 10]

 first loop:
 [2, max, 3, 1, max, max, 10]

 second loop:
 [2, -max, 3, 1, max, max, 10]
 [2, -max, -3, 1, max, max, 10]
 [-2, -max, -3, 1, max, max, 10]

 third loop:
 1 at index 3 is positive, return 3+1=4 as result.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) nums[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < nums.length; i++) {
            int num = Math.abs(nums[i]);
            if (num > nums.length) continue;
            nums[num-1] = -1*Math.abs(nums[num-1]);
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i+1;
            }
        }

        return nums.length+1;
    }
}

Explanation 3

  1. We can also use Cyclic Sort’s swapping method to solve this problem.

  2. First start from the first number nums[i] in the array. If nums[i] is within the range between 1 to nums.length, and its value nums[i] is not equal to its corresponding index nums[i]-1’s value, in other words, if nums[i] != nums[nums[i]-1], then we swap these two elements. Else, we increase i. Repeat while i is less than nums.length.

  3. Loop from the first number to the last. If the current index is not equals to current value’s corresponding index, in other words, if nums[i]-1 != i, that means we are missing the current index’s corresponding value which is i+1.

Solution 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public int firstMissingPositive(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i]-1]) {
                swap(nums, i, nums[i]-1);
            } else {
                i += 1;
            }
        }

        for (int j = 0; j < nums.length; j++) {
            if (nums[j]-1 != j) return j+1;
        }
        return nums.length+1;
    }
}