NUHMAN.com

Introduction

LeetCode 41: First Missing Positive is a problem where you're asked to find the smallest positive integer that is missing from an unsorted array. The challenge is to solve the problem with a time complexity of O(n) and a constant space complexity of O(1).

This problem requires array manipulation and involves placing numbers at their correct index positions. Once all the numbers are placed correctly, the first index that doesn't have the right number will give us the first missing positive.

Problem Statement

Given an integer array nums, find the first missing positive integer. You must implement a solution that runs in O(n) time complexity and uses O(1) extra space.

Examples

go

Input: nums = [1,2,0]
Output: 3
go

Input: nums = [3,4,-1,1]
Output: 2
go

Input: nums = [7,8,9,11,12]
Output: 1

Approach: Index Mapping

The key to solving this problem optimally is to use the array itself as a means of index mapping. Here's how we can achieve this:

Steps:

1. Filter out invalid numbers:

• Ignore numbers that are less than 1 or greater than the length of the array, as these cannot be the smallest positive missing integer.

1. Rearrange the array:

• Place each number at its correct position: For a number n (where 1 <= n <= len(nums)), place it at index n-1.
• For example, if nums[i] == 3, then place 3 at index 2 (i.e., nums[2] = 3).

1. Identify the first missing positive:

• After rearranging the array, the first index where nums[i] != i + 1 will give us the first missing positive integer.

1. If all numbers are in their correct places:

• If all numbers from 1 to n are in the correct positions, then the first missing positive is n + 1.

Go Implementation

go

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

    // Step 1: Filter out numbers that are out of the valid range [1, n]
    for i := 0; i < n; i++ {
        for nums[i] <= 0 || nums[i] > n || nums[nums[i]-1] == nums[i] {
            if nums[i] <= 0 || nums[i] > n {
                nums[i] = -1 // Mark as invalid number
            } else {
                nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] // Swap
            }
        }
    }

    // Step 2: Identify the first missing positive
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }

    // Step 3: If all numbers from 1 to n are placed correctly, return n + 1
    return n + 1
}

Example Walkthrough

Example 1:

go

Input: nums = [1, 2, 0]

1. Initial Array: [1, 2, 0]
2. Step 1 - Rearrangement: Place 1 at index 0, and 2 at index 1. The array becomes [1, 2, 0].
3. Step 2 - Find the First Missing Positive: Since index 2 has the value 0, the first missing positive is 3.
4. Output: 3

Example 2:

go

Input: nums = [3, 4, -1, 1]

1. Initial Array: [3, 4, -1, 1]
2. Step 1 - Rearrangement:

• 3 goes to index 2, 4 goes to index 3, and 1 goes to index 0. The array becomes [1, -1, 3, 4].

1. Step 2 - Find the First Missing Positive: The first index where nums[i] != i + 1 is at index 1, where nums[1] = -1. Hence, the first missing positive is 2.
2. Output: 2

Example 3:

go

Input: nums = [7, 8, 9, 11, 12]

1. Initial Array: [7, 8, 9, 11, 12]
2. Step 1 - Rearrangement: None of the numbers from 1 to 5 are present, so the array is unchanged.
3. Step 2 - Find the First Missing Positive: The first missing positive is 1.
4. Output: 1

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time Complexity: The algorithm processes each element at most twice (once during rearrangement and once during the final check), resulting in O(n) time complexity where n is the length of the array.
• Space Complexity: The solution uses only a constant amount of extra space (the rearrangement happens in-place), making the space complexity O(1).

Edge Cases

• Empty Array: If the array is empty, return 1, since the smallest positive integer is 1.
• All Negative or Zero Values: If the array contains only non-positive numbers, return 1, as it will be the first missing positive.
• Array with All Numbers: If the array contains all numbers from 1 to n, return n + 1 because there is no missing positive.

Key Takeaways

• Array Manipulation can be an efficient way to solve problems that involve finding the first missing number in a sequence.
• Rearranging the array in place allows us to avoid extra space and solve the problem with constant space complexity.
• This problem is a great example of how we can leverage index mapping to optimize the time complexity to O(n).