Skip to main content

🟥 First Missing Positive (#41)

🔗 Problem Link​

📋 Problem Statement​

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

💡 Examples​

Example 1​

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2​

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3​

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

🔑 Key Insights & Approach​

Core Observation: For an array of length n, the answer must be in the range [1, n+1]. Why? Because if all numbers 1 through n are present, the answer is n+1. Otherwise, it's the first missing number in that range.

Why In-Place Marking?

  • O(1) space constraint: Can't use a separate hash set
  • Use array as hash table: Index i represents whether number i+1 exists
  • Marking strategy: Use negative values or swapping to mark presence

The Key Insight: If we could rearrange the array so that nums[i] = i+1 for all valid positions, then the first index where nums[i] != i+1 gives us the answer.

Algorithm Steps:

  1. Place numbers in correct positions: For each number x in range [1, n], try to place it at index x-1
  2. Scan for first mismatch: First index i where nums[i] != i+1 means i+1 is missing
  3. Handle all present case: If all positions match, answer is n+1

Why This Works:

  • Negative numbers and numbers > n are irrelevant (can't be the answer)
  • We only care about numbers in range [1, n]
  • Each number has a "home" index where it belongs

Pattern Recognition: This is the "Cyclic Sort" or "Index as Hash Key" pattern - when you need O(1) space and the values have a natural mapping to indices.

🐍 Solution: Python​

Approach 1: Cyclic Sort (Optimal)​

Time Complexity: O(n) | Space Complexity: O(1)

def firstMissingPositive(nums: List[int]) -> int:
    n = len(nums)

    # Step 1: Place each number in its correct position
    # Number x should be at index x-1
    for i in range(n):
        # Keep swapping until current position has correct value
        # or value is out of range
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # Swap nums[i] to its correct position
            correct_idx = nums[i] - 1
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]

    # Step 2: Find first position where nums[i] != i+1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    # If all positions are correct, answer is n+1
    return n + 1

Approach 2: Marking with Negatives​

Time Complexity: O(n) | Space Complexity: O(1)

def firstMissingPositive(nums: List[int]) -> int:
    n = len(nums)

    # Step 1: Replace non-positive and out-of-range numbers with n+1
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1

    # Step 2: Mark presence by making value at index negative
    for i in range(n):
        val = abs(nums[i])
        if val <= n:
            # Mark index val-1 as negative (value val exists)
            if nums[val - 1] > 0:
                nums[val - 1] = -nums[val - 1]

    # Step 3: Find first positive index
    for i in range(n):
        if nums[i] > 0:
            return i + 1

    return n + 1

🔵 Solution: Golang​

Approach 1: Cyclic Sort​

Time Complexity: O(n) | Space Complexity: O(1)

func firstMissingPositive(nums []int) int {
    n := len(nums)

    // Step 1: Place each number in its correct position
    for i := 0; i < n; i++ {
        // Keep swapping until correct value or out of range
        for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            correctIdx := nums[i] - 1
            nums[i], nums[correctIdx] = nums[correctIdx], nums[i]
        }
    }

    // Step 2: Find first mismatch
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }

    return n + 1
}

Approach 2: Marking with Negatives​

Time Complexity: O(n) | Space Complexity: O(1)

func firstMissingPositive(nums []int) int {
    n := len(nums)

    // Step 1: Replace invalid numbers
    for i := 0; i < n; i++ {
        if nums[i] <= 0 || nums[i] > n {
            nums[i] = n + 1
        }
    }

    // Step 2: Mark presence
    for i := 0; i < n; i++ {
        val := abs(nums[i])
        if val <= n {
            if nums[val-1] > 0 {
                nums[val-1] = -nums[val-1]
            }
        }
    }

    // Step 3: Find first positive
    for i := 0; i < n; i++ {
        if nums[i] > 0 {
            return i + 1
        }
    }

    return n + 1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

📚 References​