41

The brute force way, would be to check for each integer from 1 to n + 1(because the answer is always in the range 1 -> n + 1), if it exists in the nums array. First one to not exist is the answer.

Time - $O(n^2)$. Space - $O(1)$.

---

Next, we can try to sort the nums array, and then we can find out in one pass, by keeping a target = 1, and incrementing this if found in the array. Finally, the target is the answer. Because if all are there, target would be incremented to n + 1 itself.

Time - $O(nlogn)$. Space - $O(1)$ (in place sorting).

---

Next, we can use a HashSet. Just fill the HashSet with elements from nums array, and then in one loop from 1 to n + 1, we check if it exists in our set. If not, it is the answer.

Time - $O(n)$. Space - $O(n)$.

---

We could have also used a boolean array instead of a HashSet. We create a bool array of size nums.Length + 1, and here each index we can assume it represents the integers. We use indices 0 -> n-1 to represent values 1 -> n.

Okay, now we pass over the nums array, and set to true in the bool array whatever positive integers we do find. Finally, the first false in the bool array will be the answer.

Time - $O(n)$. Space - $O(n)$.

---

But since, the problem itself says they need $O(n)$ time and $O(1)$ space, we must think of some optimal approach for this.

Whenever we see $O(1)$ space, we should think about how to use the given data structure itself in some meaningful way.

So, for this problem, we are given nums array. We can imagine this array having no missing positive integers. That is, we have values 1, 2, 3,.. so on inside the array starting from index 0. So, at index i, we have integer i + 1. This is the mapping of indices and integers.

Now, let us make one pass through the nums array, and for each index, we try to send this existing value ‘to its correct index’,

And for this activity, we will use a while loop. Because let’s say in at index 0, and I send the current value to its correct index, meaning, that correct index’s value is now swapped here at 0. Now, this swapped value itself must also be sent again! So we will use a while loop. As long as we can send the values to their correct index, we will do so.

Important thing, for values that are not relevant for us (those are not positive integers), we will do nothing. Relevant why? Because in our imagined mapping these values do not take part at all. So we do not know what to do with them anyway.

So, again, we make one pass in nums, and for each index, we try to send the relevant values to their correct index. And finally, when this loop completes, we can simply check first value which is not at its correct index. Because if there were no missing, each index i would have the value i + 1. So, to find out now, we make one pass again, and just check if value i + 1 is present at i index, and if not, that is the value which is missing.

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.Length; i++)
        {
	        while (nums[i] > 0 && nums[i] <= nums.Length && nums[i] != nums[nums[i] - 1])
	        {
		        int correctIndex = nums[i] - 1;
				int temp = nums[i];
				nums[i] = nums[correctIndex];
				nums[correctIndex] = temp;
	        }
        }
        
        for (int i = 0; i < nums.Length; i++)
        {
	        if (nums[i] != i + 1)
		        return i + 1;
        }
        
        return nums.Length + 1;
    }
}

Basically we are using the given array itself as a HashSet. Because, index position itself acts like the key, and the value stored there tells whether that key exists.
We use the array as a HashSet where index represents the key (x), and placing x at index x - 1 encodes its presence.

Time - $O(n)$. Space - $O(1)$.