LeetCode - First Missing Positive

Description: https://leetcode.com/problems/first-missing-positive/description/

This problem requires finding the smallest missing positive integer in an unsorted array. The key challenge is achieving %O(N)% time and %O(1)% space complexity without using extra space for hash tables.

Key insights:

• Since we're looking for the first missing positive integer, we only care about numbers in range %[1, N]%. We can mark presence of number i by making the element at index i-1 negative, effectively using the array itself as a hash table.

Algorithm steps:

1. Replace non-positive and out-of-range numbers with n+2
2. Use index i-1 to mark presence of number i by making element negative
3. First positive number's index + 1 is the answer

Here's an interactive visualization demonstrating the algorithm:

Why it works:

• Using indices as hash positions avoids extra space
• Negative markers cleverly track seen numbers
• Numbers > n can't be the answer, so safely ignored

Complexity:

• Time: %O(N)%
• Space: %O(1)%

You can find the full source code solution at https://github.com/vndee/dsa-python/blob/main/arrays/first_missing_positive.py. Please consider subscribing to my blog to stay updated with more algorithm tutorials and coding insights.