LeetCode 41. First Missing Positive

Question

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.

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

Source: https://leetcode.com/problems/first-missing-positive/

Solution

We try to put every positive number n on the position n-1. Then we traverse the array to find the first number that num[i] != i + 1, so that we get the first missing positive number. Note that there may be duplicate values that fit in the same position. We should skip the rest of them to avoid endless loop.

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

public int firstMissingPositive(int[] nums) {
    int i = 0;
    // in-place
    // num should on the num - 1 position
    // put elements to the correct position if possible
    while (i < nums.length) {
        int num = nums[i];
        if (num <= 0 || num == i + 1 || num - 1 >= nums.length) { // skip
            i++;
        } else if (num == nums[num - 1]) { // multiple elements fit the same position
            // prevent endless loop
            i++;
        } else {
            // do not update i here
            swap(nums, i, num - 1);
        }
    }
    i = 0;
    for (; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            break;
        }
    }
    return i + 1;
}