First Missing Positive - Video Solutions

Problem Overview: Given an unsorted integer array, return the smallest missing positive integer. The challenge is achieving O(n) time while using O(1) extra space. Negative numbers and values larger than the array length must be ignored since they cannot affect the smallest missing positive within the range 1..n+1.

Approach 1: Hash Concept with Array (O(n) time, O(n) space)

This approach uses an auxiliary array or boolean marker structure to record which positive numbers appear in the input. First iterate through the array and mark presence for every number x where 1 ≤ x ≤ n. After marking, perform a second pass from index 1 to n to find the first index that was never marked. That index represents the smallest missing positive. The key insight is that the answer must lie within 1..n+1, so tracking only that range is sufficient. This method is simple and reliable but uses additional memory proportional to the input size, which violates the strict constant-space requirement often expected in interviews involving Hash Table style presence tracking.

Approach 2: Cyclic Sort (O(n) time, O(1) space)

The optimal approach places each number in its "correct" index using swaps. For an array of length n, the number x should ideally appear at index x-1. Iterate through the array and repeatedly swap elements until each valid number is either placed in its correct position or determined to be out of range. Only numbers between 1 and n participate in this placement step. After the rearrangement, perform a final pass: the first index i where nums[i] != i + 1 reveals the smallest missing positive. If every index is correct, the answer is n + 1. This technique relies on in-place swaps similar to cyclic sort, making it a classic Array manipulation problem that avoids extra memory.

The core insight is that the array itself can act as a hash structure. Instead of storing presence externally, you encode the presence of value x by placing it at position x-1. Each element moves at most once or twice, which keeps the total number of operations linear.

Recommended for interviews: The cyclic sort approach is the expected solution because it achieves O(n) time with O(1) extra space. Interviewers typically look for the realization that only numbers within 1..n matter and that the array can be rearranged to track presence. The hash-based approach demonstrates understanding of the problem constraints, but the in-place technique shows stronger mastery of array indexing tricks and space optimization.