Skip to main content
Talentd

First Missing Positive - Solution & Explanation

HardArrayHash Table21 min readAsked at: Amazon, Microsoft, Apple +30
Practice this problem

Problem Statement

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

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

 

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.

 

Constraints:

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

Approach Overview

Problem Overview: You are given an unsorted integer array. The goal is to find the smallest positive integer that does not appear in the array. The challenge is handling negative numbers, duplicates, and large values while keeping the solution efficient.

Approach 1: Sorting the Array (O(n log n) time, O(1) extra space)

A straightforward strategy is to sort the array first, then scan from left to right looking for the first gap in positive integers. After sorting, maintain a variable representing the smallest expected positive value starting at 1. Iterate through the array and update this expected value whenever you encounter it. When the expected number is skipped, that value is the missing positive. This approach is simple to reason about but sorting introduces O(n log n) time complexity, which is slower than the optimal linear solution.

Approach 2: Hash Concept with Array (O(n) time, O(n) space)

This method uses a boolean array or hash-based presence tracking. Create a structure of size n + 1 (where n is the input size) and mark whether each positive number in the range [1, n] appears in the input. Iterate through the original array and mark valid numbers. Then scan the tracking array starting from index 1; the first unmarked index is the missing positive. Any number larger than n can be ignored because the answer must fall within [1, n+1]. This technique relies on constant-time hash lookups and sequential iteration, producing O(n) time complexity but requiring additional memory.

Approach 3: Cyclic Sort / Index Placement (O(n) time, O(1) space)

The optimal approach uses an index-placement idea often associated with cyclic sort. Since the smallest missing positive must lie in the range [1, n+1], each value x ideally belongs at index x - 1. Iterate through the array and repeatedly swap elements so that valid numbers are placed at their correct indices. For example, if the current value is 3, swap it with the element at index 2. Continue swapping until the current number is either out of range, already positioned correctly, or a duplicate. After this placement pass, run another scan: the first index i where nums[i] != i + 1 reveals the missing positive i + 1. If all positions are correct, the answer is n + 1. This method modifies the array in-place and achieves O(n) time with O(1) extra space.

Recommended for interviews: The cyclic sort approach is the one most interviewers expect because it satisfies the strict constraints of O(n) time and constant extra space. Starting with the hash-based method demonstrates clear reasoning about the range of possible answers, but recognizing that the array itself can act as the storage structure shows deeper algorithmic skill. Problems like this commonly appear in discussions around array manipulation and hash table style presence tracking.

Approach 1: Cyclic Sort

This approach utilizes the cyclic sort algorithm to place numbers in their corresponding indices. For example, 1 should be at index 0, 2 should be at index 1, etc. While rearranging, we ignore numbers outside the range [1, n], where n is the length of the array.

After rearranging, the first index i that doesn’t have a number i+1 indicates the smallest missing positive integer.

The function iterates over the array, swapping elements within the valid range to their correct positions. It then checks for the first missing positive by assessing incorrect positions.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as each number is swapped at most once.
Space Complexity: O(1), as no additional space is used apart from variables.

Try this approach in the editor →

Approach 2: Hash Concept with Array

By assuming the input array itself can act like a hash map, this approach assigns each index with a corresponding positive value within the range. If out of range, we fill that index with a placeholder number like the array size + 1.

We then use index signs to mark present numbers and deduce the missing positive from the invalid marked position.

Remove out of range numbers by filling them with the max possible value. Using negative marking helps identify seen numbers within the range, returning the first positive marked index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: 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.

After the traversal, we traverse the array again. If i+1 is not equal to nums[i], then i+1 is the smallest positive integer we are looking for.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC#CPHP

Python

Java

C++

Go

TypeScript

Rust

C#

C

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Cyclic Sort

Time Complexity: O(n), as each number is swapped at most once.
Space Complexity: O(1), as no additional space is used apart from variables.

Hash Concept with Array

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

In-place Swap—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
SortingO(n log n)O(1)Quick baseline solution when optimal constraints are not required
Hash Concept with ArrayO(n)O(n)Simple linear solution using presence tracking
Cyclic Sort (Index Placement)O(n)O(1)Best interview solution when constant extra space is required

Video Solution

First Missing Positive - Leetcode 41 - Python • NeetCode • 167,858 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is First Missing Positive easy or hard?
First Missing Positive is classified as a Hard problem because it requires recognizing that the answer must lie in the range [1, n+1] and using that insight to design an in-place O(n) algorithm with constant extra space.
First Missing Positive Python/Java solution
Python and Java implementations typically follow the cyclic sort idea. Iterate through the array and swap elements until each valid value is placed at index value-1. Then perform a linear scan to find the first index where the expected value is missing.
How to solve First Missing Positive in O(n)?
Use index placement. Iterate through the array and swap numbers so each value x goes to position x-1 whenever 1 ≤ x ≤ n. After all valid numbers are placed, scan the array again; the first position where nums[i] is not equal to i+1 gives the missing positive integer.
What is the best approach for First Missing Positive?
The cyclic sort (index placement) approach is considered the best solution. It places each number x at index x-1 if it falls within the range [1, n]. After rearranging, the first index where nums[i] != i+1 reveals the missing positive. This runs in O(n) time and uses O(1) extra space.
Is First Missing Positive asked at Google/Amazon/Meta?
First Missing Positive frequently appears in interviews at large tech companies including Google, Amazon, and Meta. The problem tests in-place array manipulation, constraint reasoning, and the ability to achieve linear time with constant extra space.
What data structure is used in First Missing Positive?
The problem primarily uses array manipulation techniques. Some solutions rely on hash-style presence tracking with an auxiliary array, while the optimal approach treats the input array itself as a placement structure using cyclic swaps.
What is the time complexity of First Missing Positive?
The optimal solution runs in O(n) time with O(1) extra space using the cyclic sort technique. Alternative solutions include a hash-based presence array with O(n) time and O(n) space, or a sorting approach with O(n log n) time.

Ready to solve this problem?

Practice First Missing Positive with our built-in code editor and test cases.

Practice on FleetCode
Previous

Couples Holding Hands

Next

Find All Numbers Disappeared in an Array