#41

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

First Missing Positive

Identify the smallest missing positive integer in an unsorted array using constant space and linear time scanning techniques.

array hash table

Problem Statement

Given an unsorted integer array nums, return the smallest positive integer that does not appear in nums. You must achieve this without using extra arrays or hash sets beyond constant space.

For example, given nums = [3,4,-1,1], the smallest missing positive is 2. Your solution must run in linear time, so naive sorting or additional memory usage will not meet the constraints.

Examples

Example 1

Input: nums = [1,2,0]

Output: 3

The numbers in the range [1,2] are all in the array.

Example 2

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

Output: 2

1 is in the array but 2 is missing.

Example 3

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

Output: 1

The smallest positive integer 1 is missing.

Constraints

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1

Solution Approach

In-Place Index Mapping

Iterate through the array and for each number x in the range [1, n], place it at index x-1 by swapping. This positions all possible positive integers in their corresponding slots.

Detect the First Gap

After index mapping, scan the array from left to right. The first index i where nums[i] != i+1 indicates that i+1 is missing. This directly identifies the smallest missing positive.

Handle Edge Cases

If all numbers from 1 to n are present, return n+1. This handles arrays filled with consecutive positives or arrays containing only negative numbers or zeros.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each element is swapped at most once. Space complexity is O(1) since swaps are done in-place and no extra arrays or hash tables are used.

What Interviewers Usually Probe

Focuses on in-place reordering and mapping to indices.
Checks if candidate solutions avoid extra memory usage.
Wants candidates to handle negatives, zeros, and large positive gaps correctly.

Common Pitfalls or Variants

Common pitfalls

Swapping incorrectly can lead to infinite loops or missed numbers.
Ignoring numbers outside [1,n] range causes wrong results.
Failing to return n+1 when all slots 1..n are filled.

Follow-up variants

Find the first missing positive when duplicates exist in nums.
Find all missing positives up to the maximum number in the array.
Find missing positives under memory constraints stricter than O(1).

FAQ

What is the main strategy to solve First Missing Positive?

Use in-place index mapping by swapping each number x to index x-1 and then scan to find the first mismatch.

Why is O(1) space important for this problem?

The problem specifically requires constant auxiliary space to test understanding of in-place array manipulation.

How do negatives or zeros affect the solution?

Negatives and zeros are ignored during swaps since only positive integers in the range 1..n are relevant.

Can duplicates in the array break the algorithm?

No, duplicates are safely ignored during swaps as long as numbers are positioned correctly in their index slots.

What pattern does this problem exemplify?

This problem demonstrates the array scanning plus hash lookup pattern where positions are used as implicit hash keys.

terminal

Solution

Solution 1: In-place Swap

We assume the length of the array $nums$ is $n$, then the smallest positive integer must be in the range $[1, .., n + 1]$. We can traverse the array and swap each number $x$ to its correct position, that is, the position $x - 1$. If $x$ is not in the range $[1, n + 1]$, then we can ignore it.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

Continue Practicing

#37 sudoku solver #36 valid sudoku #49 group anagrams