This is a leetcode hard level problem. It is not very hard if you don't care about time and space complexity. It is the optimization technique that make this problem interesting.

To solve this problem, the first pattern we need to find is how many steps we need to take to make it to the first missing positive value. This may seems impossible to know at first, because we don't know what value in the array. The value may be very big, so we may need to try a lot of numbers. Actually, it is not. Take a look a below examples.

[-3,-2,-1,1], first missing positive => 2
[1,2,4,5], first missing positive => 3
[1,2,3,4,5], first missing positive => 6

As you can see, because the length of the array limits the options, so the max value of the first missing positive is just length+1. So what we need to do is just iterate from 1 to length+1, and check if current value in the array, then we can get the result.

So, we can write a solution like below.

function firstMissingPositive(nums: number[]): number {
    nums = nums.filter(num => num > 0);
    const nset = new Set(nums);

    for (let i = 1; i <= nums.length; i++) {
        if (!nset.has(i)) return i;
    }

    return nums.length + 1;
};

The time complexity is O(n), its acceptable. But it also takes O(n) space complexity. How can we only use constant space to solve this problem? Then its the interesting part comes.

Let's think about again what we want. we want a data structure to tell us if nums from 1 to length+1 exists in the original array. In the above code, we use a Set to store this information. Actually, we can use the original nums array to store this information too.

The key idea is, we use the original nums array's index as the key, and nums array's values as the value. For example, if 2 is in the array, then we make the value nums[2] to be negative. If 2 is not in the array, we make the value nums[2] to be positive.

That is clever, we can use this positive and negative to store if a num in the nums array. But why? why should we want do this? What is the merit behind this positive and negative thing? Well, think again. When we use the value of the nums array to store another information, we need to change the value somehow. But at some point, we need to access the original value as well. So, this is the reason. By making values negative, we know the index of the value exist, and later we can convert it back to original value easily.

Besides, there are also 1 thing needs to be noted. How should we handle the original negative values? we need to use negative to tell us some information later, so we need to make them positive first. But if we make them positive, then they will confuse with normal postive values. So to solve this, we can make them all as value 1. And then we handle value 1 independently to solve this confusion.

With all this in mind, then we can come up with this O(1) space solution.

function firstMissingPositive(nums: number[]): number {
    // handle value 1 first
    if (!nums.some(num => num === 1)) return 1;

    nums = nums.map(num => num > 0 ? num : 1);

    for (let i = 0; i < nums.length; i++) {
        const num = Math.abs(nums[i]);
        if (num <= 1) continue; // don't care value 1
        if (num > nums.length) continue; // don't care big values, beyond answer range
        // here, we move left, num => nums[num-1], then we can store length => nums[length-1]
        if (nums[num - 1] < 0) continue; // only set negative once
        nums[num - 1] *= -1;
    }

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

    return nums.length + 1;
};

This technique is very useful. The key idea is to use the data structure we already have to store another information. If we don't care about original value, then its done. If we do want to access original value later, then we need to find a way to store both of them.