First Missing Positive

I would ask: can the array hold negatives, zeros and duplicates? How large can the values be? May I rearrange or overwrite the input, or must it stay intact? Does "constant extra space" rule out a hash set? What should come back for an empty array, or when the array holds exactly 1 through n?

I would assume yes to negatives, zeros and duplicates, huge values allowed, rearranging the input is permitted, a hash set is not, an empty array gives 1, and an array containing 1 through n gives n + 1.

Test candidates in order: for k = 1, 2, 3, scan the whole array to see whether k is present, and stop at the first miss. If the array holds 1 through n, that is n scans of n elements, so O(n²). With n = 100,000 that is ten billion comparisons.

Two quick improvements each break a rule. Putting all values in a hash set gives O(n) time but O(n) extra memory. Sorting (with a numeric comparator) and walking through costs O(n log n) time, and it is O(1) extra only with an in-place sort such as heapsort, since the built-in sort is not guaranteed to be in place. The problem asks for both linear time and constant space, so the array itself has to act as the lookup table.

The pattern is in-place hashing by index, also called cyclic sort. The first observation is a counting one: with n numbers, the answer must lie in 1 to n+1. If every number from 1 to n appears, the array is a rearrangement of exactly those, so the answer is n+1; otherwise some k at most n is missing. Anything below 1 or above n can never matter, so we ignore it.

That gives a perfect hash: value v belongs at index v-1. Go through the positions. While the value at position i is between 1 and n and its home slot does not already hold that value, swap it into its home slot. The "does not already hold" check, made against the home slot, is what makes duplicates safe, because a repeated value finds its slot taken and stops.

After the pass, scan once: the first slot i whose value is not i+1 means i+1 is missing, because if i+1 had been in the array it would have been placed in slot i. If every slot is right, return n+1.

The nested loop is still linear: each swap puts one value into its final slot for good, so there are at most n swaps in total, and every value that is skipped is skipped once. I would say it aloud as: send each number home, then see which home is empty.

Use [5,2,-1,1,3,3], so n = 6. The trace table logs each decision with the array afterwards.

At position 0 the value 5 belongs at slot 4, which holds 3, so swap: [3,2,-1,1,5,3]. The 3 now at position 0 belongs at slot 2, which holds -1, so swap: [-1,2,3,1,5,3]. The -1 is out of range, so move on. Positions 1 and 2 hold 2 and 3, already home. At position 3 the value 1 belongs at slot 0, which holds -1, so swap: [1,2,3,-1,5,3]; the new -1 is skipped. Position 4 holds 5, home. Position 5 holds a second 3 whose slot already holds 3, so it is skipped. The scan finds slot 3 holding -1 instead of 4, so the answer is 4.

An empty array has n = 0, both loops do nothing, and the answer is 1. An array like [2] gives 1 because slot 0 does not hold 1; [1] gives 2. All negatives or zeros leave every slot wrong, so slot 0 reports 1.

Duplicates such as [1,1] do not loop forever, since the second 1 finds slot 0 already holding 1. Huge values like 10^9 fail the range test and are skipped, so nothing is read out of bounds. An array that is a permutation of 1 to n passes the scan and returns n+1. The function rearranges its input, which the problem allows; the answer would be the same for any ordering of the same values.

Number one is an infinite loop on duplicates: comparing the value to its own position, instead of to the value in the home slot, never stops for [1,1]. Number two is a JavaScript trap with the swap itself. Writing [nums[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]] reassigns nums[i] first, so the second target index is computed from the new value and the swap corrupts the array. Compute the home index into a variable before swapping.

Also common: off-by-one between value and index (v goes to v-1), only advancing the index after one swap so some values are never examined, forgetting the n+1 case, reaching for a Set that breaks the memory rule, and ignoring values greater than n and indexing outside the array.