41. First Missing Positive

Sorting

class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int last = 0; 
        for (int i = 0; i < n; i++) {
            int cur = nums[i];

            // only process positive nums
            if (cur <= 0 || cur == last) continue;

            // if the current num is not expected
            if (cur != last + 1) {
                return last + 1;
            }
            // update last
            last = cur;
        }

        // all nums appeared
        return last + 1;
    }
}

Remarks:

1. Be careful of the boundaries.
2. TC: $O(n\log n)$ (because we used Array.sort). This does not satisfy the requirement.

Swap Number

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Step 1: place each number at the corresponding plaec（x -> nums[x - 1]）
        for (int i = 0; i < n; i++) {
            while (
                nums[i] > 0 && nums[i] <= n &&  // valid positive int
                nums[nums[i] - 1] != nums[i]    // wrong position
            ) {
                // swap nums[i] and nums[nums[i] - 1]
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        // Step 2: find the first one doesn't satisfy nums[i] == i + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // if all numbers satisfies
        return n + 1;
    }
}

Remarks:

1. TC: $O(n)$. Although there’s a while loop in each for, all numbers will be only swapped at most once to be placed at their correct position.