LeetCode - First Missing Positive

DUY HUYNH -

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:

Original Array:
Step 1: Replace non-positive and too large numbers by %N + 2%
Step 2: Mark positions by making numbers negative
Step 3: Find first positive number

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.