First Missing Postive solution

The official solution requires a 3-pass array traverse, and is easy to get wrong when coding.

I learnt and developed a better solution is based on two-pointers and loop invariant.

class Solution {
    public int firstMissingPositive(int[] nums) {
        int left = 0, right = nums.length;
        while (left < right) {
            if (nums[left] == left + 1) {
                ++left;
            } else if (nums[left] <= left || nums[left] > right || nums[left] == nums[nums[left] - 1]) {
                nums[left] = nums[--right];
            } else {
                nums[left] = nums[nums[left] - 1] ^ nums[left] ^ (nums[nums[left] - 1] = nums[left]);
            }
        }
        return right + 1;
    }
}

Explanations:

• On the left side, we already see the number left. The expected number is more significant than the left.
• On the right side, the right is the largest possible answer.
  • Initially, the best answer is nums. length + 1, when all element range from 1 to nums. length and no repetition.
  • If nums[left] == left + 1, we should mark it and increase left border
  • In following three conditions, we reduce right border and put rightmost element to check in the next loop;
    • If any number is out of range (left, right)(both are exclusive), we wasted one potential answer slot. So right shall be minus by one;
    • If any number is in range (left, right) but already seen, it also means one potential answer slot is wasted.
    • If the above two condition is not satisfied, the number-on-checking ranges from [left + 1, right]. If we got nums[left] == nums[nums[left] - 1], it means one repetition is shown, so one slot is also wasted.
  • If above situation is not satisfied, it’s means nums[left](the checked one) is range in [left + 1, right) and no repetition found. We need to put it in right position and check it again in next loop;

A more clear expression:

public int firstMissingPositive(int[] nums) {
        int left = 0, right = nums.length;
        while (left < right) {
            if (nums[left] == left + 1) {
                ++left;
            } else if (nums[left] <= left || nums[left] > right) {
                nums[left] = nums[--right];
            } else {
                if (nums[left] == nums[nums[left] - 1]) {
                    nums[left] = nums[--right];
                } else {
                    nums[left] = nums[nums[left] - 1] ^ nums[left] ^ (nums[nums[left] - 1] = nums[left]);
                }
            }
        }
        return left + 1;
    }