LeetCode 41: First Missing Positive Solution in Python Explained

Problem Statement

LeetCode 41, First Missing Positive, is a hard-level problem where you’re given an unsorted integer array nums. Your task is to find the smallest positive integer (greater than 0) that does not appear in the array. The solution must run in O(n) time complexity and use O(1) extra space, meaning no additional arrays or hash tables are allowed.

Constraints

1 <= nums.length <= 10^5: Array length is between 1 and 100,000.
-2^31 <= nums[i] <= 2^31 - 1: Elements are within 32-bit signed integer range.

Example

Input: nums = [1,2,0]
Output: 3
Explanation: 1 and 2 are present, 0 is not positive, so 3 is the first missing positive.

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is present, 2 is missing, 3 and 4 are present.

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: No positive integers from 1 to 6 are present, so 1 is missing.

Understanding the Problem

How do you solve LeetCode 41: First Missing Positive in Python? For nums = [3,4,-1,1], the smallest missing positive is 2 because 1 is present, but 2 isn’t. We need an O(n) solution with O(1) space, so we can’t sort or use extra storage. We’ll explore two approaches: an In-Place Hashing Solution (optimal and primary) and an Alternative with Sorting (intuitive but O(n log n)). The in-place method uses the array itself as a hash table by placing numbers in their correct indices.

Solution 1: In-Place Hashing Approach (Primary)

Explanation

Since we’re looking for the smallest missing positive integer in an array of length n, the answer must be between 1 and n+1 (if all 1 to n are present). Use the array as a hash table: for each number x, place it at index x-1 if 1 ≤ x ≤ n. After arranging, the first index where nums[i] != i+1 indicates the missing number.

Here’s a flow for [3,4,-1,1]:

Initial: [3,4,-1,1]
Place 1: [1,4,-1,3]
Place 3: [1,4,3,-1]
Place 4: [1,4,3,-1]
Check: nums[1] = 4 != 2, missing 2

Ignore Irrelevant Numbers.

Replace numbers < 1 or > n with 1 (or skip).

Place Numbers.

Swap each number to its correct index (num-1).

Find Missing.

Scan for first mismatch.

Return Result.

If all match, return n+1.

Step-by-Step Example

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

We need 2.

Goal: Find first missing positive.
Result for Reference: 2.
Start: nums = [3,4,-1,1], n = 4.
Step 1: Replace -1 (irrelevant) with 1.

nums = [3,4,1,1].

Step 2: Place numbers.

i = 0, 3, swap with index 2, nums = [1,4,3,1].
i = 0, 1, already correct.
i = 1, 4, swap with index 3, nums = [1,1,3,4].
i = 2, 3, swap with index 2, nums = [1,1,3,4].

Step 3: Check.

i = 0, nums[0] = 1 = 0+1, ok.
i = 1, nums[1] = 1 != 2, missing 2.

Finish: Return 2.

Example 2: nums = [1,2,0]

We need 3.

Start: Replace 0 with 1, nums = [1,2,1].
Step 1: Place numbers.

All in place or duplicates, nums = [1,2,1].

Step 2: Check.

i = 0, 1 = 1, ok.
i = 1, 2 = 2, ok.
i = 2, 1 != 3, missing 3.

Finish: Return 3.

How the Code Works (In-Place Hashing)

Here’s the Python code with line-by-line explanation:

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

    # Line 1: Replace non-positive and > n with 1
    contains_one = False
    for i in range(n):
        if nums[i] == 1:
            contains_one = True
        elif nums[i] <= 0 or nums[i] > n:
            nums[i] = 1

    # Line 2: If no 1, return 1
    if not contains_one:
        return 1

    # Line 3: Use array as hash table
    for i in range(n):
        # Line 4: Get absolute value (in case marked negative)
        idx = abs(nums[i]) - 1
        # Line 5: Mark presence by making negative
        if nums[idx] > 0:
            nums[idx] = -nums[idx]

    # Line 6: Find first missing positive
    for i in range(n):
        if nums[i] > 0:
            return i + 1

    # Line 7: All 1 to n present, return n+1
    return n + 1

Alternative: Sorting Approach

Explanation

Sort the array and scan for the first missing positive. This is O(n log n) and doesn’t meet the O(n) requirement but is intuitive for understanding.

Sort Array.
Scan for Missing.
Return Result.

Step-by-Step Example (Alternative)

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

Goal: 2.
Step 1: Sort, nums = [-1,1,3,4].
Step 2: Scan.

i = 0, -1, skip.
i = 1, 1, expect 1, ok.
i = 2, 3, expect 2, missing 2.

Finish: Return 2.

How the Code Works (Sorting)

def firstMissingPositiveSort(nums: list[int]) -> int:
    # Line 1: Sort array
    nums.sort()

    # Line 2: Initialize expected positive
    expected = 1

    # Line 3: Scan for missing
    for num in nums:
        if num <= 0:
            continue
        if num == expected:
            expected += 1
        elif num > expected:
            return expected

    # Line 4: Return next if all present
    return expected

Complexity

In-Place Hashing:

Time: O(n) – Two passes through array.
Space: O(1) – No extra space.

Sorting:

Time: O(n log n) – Sorting dominates.
Space: O(1) – In-place sort (Python’s Timsort uses O(n) internally, but we assume O(1) for problem context).

Efficiency Notes

In-Place Hashing meets O(n) time and O(1) space, making it ideal for LeetCode 41. Sorting is O(n log n) and simpler but fails the time constraint.

Key Insights

Tips to master LeetCode 41:

Array as Hash: Use indices to mark presence.
Range Focus: Answer is 1 to n+1, ignore others.
In-Place Magic: Modify array cleverly.

Additional Example

For nums = [1,2,3]:

Goal: 4.
In-Place: [1,2,3], all match, return 4.
Result: 4.

Edge Cases

All Negative: [-1,-2] – Return 1.
Single Element: [1] – Return 2.
No Gaps: [1,2,3] – Return 4.

Final Thoughts

The In-Place Hashing solution is a brilliant fit for LeetCode 41 in Python—tricky but efficient, perfect for O(n) and O(1) constraints. For a related challenge, try LeetCode 40: Combination Sum II to switch gears with combinations! Ready to find the missing number? Solve LeetCode 41 on LeetCode now and test it with arrays like [1,3,4] or [-1,2,5] to sharpen your skills. Dive in and solve it!