First Missing Positive

First Missing Positive

1. What is this problem about?

The First Missing Positive interview question is a famous "Hard" level array problem. You are given an unsorted integer array, and you need to find the smallest positive integer ($1, 2, 3 \dots$) that is not present in the array. The catch is that you must solve it in $O(N)$ time and $O(1)$ extra space.

2. Why is this asked in interviews?

This is a staple question at high-tier companies like Amazon, Meta, and Netflix. It tests whether a candidate can use the input array itself as a hash map. It evaluates your ability to perform In-place array manipulation and handle edge cases like negative numbers, zeros, and large values. It's a true test of algorithmic creativity under strict constraints.

3. Algorithmic pattern used

The optimal solution uses the Cycle Sort / Bucket Sort pattern (specifically, placing each number $X$ at index $X-1$).

1. Placement: Iterate through the array. For each number $x$ that is in the range $[1, n]$, try to swap it with the element at index $x-1$.
2. Logic: Keep swapping until nums[i] is either out of range or already at the correct index (nums[i] == nums[nums[i] - 1]).
3. Verification: After one pass, iterate through the array again. The first index $i$ where nums[i] != i + 1 tells you that $i+1$ is the first missing positive.
4. Default: If all indices $0 \dots n-1$ contain $1 \dots n$, the missing number is $n+1$.

4. Example explanation

Array: [3, 4, -1, 1]

1. index 0 (value 3): Swap with index 2. Array: [-1, 4, 3, 1].
2. index 0 (-1): Out of range. Move to index 1.
3. index 1 (4): Swap with index 3. Array: [-1, 1, 3, 4].
4. index 1 (1): Swap with index 0. Array: [1, -1, 3, 4].
5. Verification:
   • index 0: 1. (Correct)
   • index 1: -1. (Should be 2). Result: 2.

5. Common mistakes candidates make

• Using a Set: Using $O(N)$ extra space, which fails the $O(1)$ constraint.
• Sorting: Using $O(N \log N)$ time, which fails the $O(N)$ requirement.
• Infinite Swaps: Forgetting the condition nums[i] != nums[nums[i]-1], which leads to an infinite loop if the array has duplicates.

6. Interview preparation tip

Master the "Value as Index" technique. It is the most common way to achieve $O(1)$ space in problems involving numbers within a restricted range ($1 \dots N$). Practice this alongside the "Negation Marking" trick.