First Missing Positive - Video Solutions

Problem Overview: You are given an unsorted integer array. The goal is to find the smallest positive integer that does not appear in the array. The challenge is handling negative numbers, duplicates, and large values while keeping the solution efficient.

Approach 1: Sorting the Array (O(n log n) time, O(1) extra space)

A straightforward strategy is to sort the array first, then scan from left to right looking for the first gap in positive integers. After sorting, maintain a variable representing the smallest expected positive value starting at 1. Iterate through the array and update this expected value whenever you encounter it. When the expected number is skipped, that value is the missing positive. This approach is simple to reason about but sorting introduces O(n log n) time complexity, which is slower than the optimal linear solution.

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

This method uses a boolean array or hash-based presence tracking. Create a structure of size n + 1 (where n is the input size) and mark whether each positive number in the range [1, n] appears in the input. Iterate through the original array and mark valid numbers. Then scan the tracking array starting from index 1; the first unmarked index is the missing positive. Any number larger than n can be ignored because the answer must fall within [1, n+1]. This technique relies on constant-time hash lookups and sequential iteration, producing O(n) time complexity but requiring additional memory.

Approach 3: Cyclic Sort / Index Placement (O(n) time, O(1) space)

The optimal approach uses an index-placement idea often associated with cyclic sort. Since the smallest missing positive must lie in the range [1, n+1], each value x ideally belongs at index x - 1. Iterate through the array and repeatedly swap elements so that valid numbers are placed at their correct indices. For example, if the current value is 3, swap it with the element at index 2. Continue swapping until the current number is either out of range, already positioned correctly, or a duplicate. After this placement pass, run another scan: the first index i where nums[i] != i + 1 reveals the missing positive i + 1. If all positions are correct, the answer is n + 1. This method modifies the array in-place and achieves O(n) time with O(1) extra space.

Recommended for interviews: The cyclic sort approach is the one most interviewers expect because it satisfies the strict constraints of O(n) time and constant extra space. Starting with the hash-based method demonstrates clear reasoning about the range of possible answers, but recognizing that the array itself can act as the storage structure shows deeper algorithmic skill. Problems like this commonly appear in discussions around array manipulation and hash table style presence tracking.