First Missing Positive solution and explanation
Google
9 more videos on this problem
First Missing Positive - Leetcode 41 - PythonNeetCode · 21:22 · 167K views
First Missing Positive || Intuition + Example + Explanation || Must Do for AmazonCode with Alisha · 19:58 · 35K views
First Missing Positive | LeetCode 41 | C++, Java, Python | BITWISE operationKnowledge Center · 16:24 · 29K views
First Missing Positive | In Depth Intuition | Clean Code | Leetcode 41 | codestorywithMIKcodestorywithMIK · 33:17 · 24K views
(Old) Leetcode 41 - Arrays | First Missing PositiveNideesh Terapalli · 6:37 · 8K views
First Missing Positive (LeetCode 41) — Marked "Hard" but the Trick is Embarrassingly SimpleNikhil Lohia · 17:26 · 4K views
First Missing Positive | Leet code 41 | Theory explained + Python codeSai Anish Malla · 14:41 · 2K views
FIRST MISSING POSITIVE | LEETCODE # 41 | PYTHON SOLUTIONCracking FAANG · 24:12 · 2K views
First Missing Positive - Leetcode 41 - JavaMastering Programming · 10:08 · 1K views
UChicago ICPC - Arrays - Leetcode 41 First Missing Positive - O(1) spaceFaradawn Yang · 9:58 · 1K views
The problem
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.
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
while 0 < nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
nums = [3, 4, -1, 1]
print(f"The first missing positive is {first_missing_positive(nums)}")import java.util.*;
class FirstMissingPositive {
public static int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
public static void main(String[] args) {
int[] nums = {3, 4, -1, 1};
System.out.println("The first missing positive is " + firstMissingPositive(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
int main() {
vector<int> nums = {3, 4, -1, 1};
cout << "The first missing positive is " << firstMissingPositive(nums) << endl;
return 0;
}function firstMissingPositive(nums) {
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
[nums[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]];
}
}
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) {
return i + 1;
}
}
return n + 1;
}
const nums = [3, 4, -1, 1];
console.log(`The first missing positive is ${firstMissingPositive(nums)}`);#include <stdio.h>
int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; i++) {
while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < numsSize; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return numsSize + 1;
}
int main() {
int nums[] = {3, 4, -1, 1};
int size = sizeof(nums) / sizeof(nums[0]);
int result = firstMissingPositive(nums, size);
printf("The first missing positive is %d\n", result);
return 0;
}using System;
class FirstMissingPositiveSolution {
public static int FirstMissingPositive(int[] nums) {
int n = nums.Length;
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
static void Main() {
int[] nums = {3, 4, -1, 1};
Console.WriteLine("The first missing positive is " + FirstMissingPositive(nums));
}
}In Python, the code swaps elements to their rightful indexes if they fall within the bounds, then searches for the first missing number.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
if nums[i] <= 0 or nums[i] > n:
nums[i] = n + 1
for i in range(n):
num = abs(nums[i])
if num <= n:
nums[num - 1] = -abs(nums[num - 1])
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1
nums = [3, 4, -1, 1]
print(f"The first missing positive is {first_missing_positive(nums)}")import java.util.*;
class FirstMissingPositive {
public static int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = n + 1;
}
}
for (int i = 0; i < n; i++) {
int num = Math.abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
public static void main(String[] args) {
int[] nums = {3, 4, -1, 1};
System.out.println("The first missing positive is " + firstMissingPositive(nums));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = n + 1;
}
}
for (int i = 0; i < n; ++i) {
int num = abs(nums[i]);
if (num <= n) {
nums[num - 1] = -abs(nums[num - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
int main() {
vector<int> nums = {3, 4, -1, 1};
cout << "The first missing positive is " << firstMissingPositive(nums) << endl;
return 0;
}function firstMissingPositive(nums) {
const n = nums.length;
for (let i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = n + 1;
}
}
for (let i = 0; i < n; i++) {
const num = Math.abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
for (let i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
const nums = [3, 4, -1, 1];
console.log(`The first missing positive is ${firstMissingPositive(nums)}`);#include <stdio.h>
#include <stdlib.h>
int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; i++) {
if (nums[i] <= 0 || nums[i] > numsSize) {
nums[i] = numsSize + 1;
}
}
for (int i = 0; i < numsSize; i++) {
int num = abs(nums[i]);
if (num <= numsSize) {
nums[num - 1] = -abs(nums[num - 1]);
}
}
for (int i = 0; i < numsSize; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return numsSize + 1;
}
int main() {
int nums[] = {3, 4, -1, 1};
int size = sizeof(nums) / sizeof(nums[0]);
int result = firstMissingPositive(nums, size);
printf("The first missing positive is %d\n", result);
return 0;
}using System;
class FirstMissingPositiveSolution {
public static int FirstMissingPositive(int[] nums) {
int n = nums.Length;
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = n + 1;
}
}
for (int i = 0; i < n; i++) {
int num = Math.Abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.Abs(nums[num - 1]);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
static void Main() {
int[] nums = {3, 4, -1, 1};
Console.WriteLine("The first missing positive is " + FirstMissingPositive(nums));
}
}This Python technique replaces invalid numbers with n+1, flips valid indexed numbers negatively, and uncovers the first sign-unflipped index as the missing positive.
Time Complexity: O(n)
Space Complexity: O(1)
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).
function firstMissingPositive(nums: number[]): number {
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] !== nums[nums[i] - 1]) {
const j = nums[i] - 1;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) {
return i + 1;
}
}
return n + 1;
}func firstMissingPositive(nums []int) int {
n := len(nums)
for i := range nums {
for 0 < nums[i] && nums[i] <= n && nums[i] != nums[nums[i]-1] {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
}
}
for i, x := range nums {
if x != i+1 {
return i + 1
}
}
return n + 1
}impl Solution {
pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
let n = nums.len();
for i in 0..n {
while nums[i] > 0 && nums[i] <= n as i32 && nums[i] != nums[nums[i] as usize - 1] {
let j = nums[i] as usize - 1;
nums.swap(i, j);
}
}
for i in 0..n {
if nums[i] != (i + 1) as i32 {
return (i + 1) as i32;
}
}
return (n + 1) as i32;
}
}class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function firstMissingPositive($nums) {
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
while ($nums[$i] >= 1 && $nums[$i] <= $n && $nums[$i] != $nums[$nums[$i] - 1]) {
$j = $nums[$i] - 1;
$t = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $t;
}
}
for ($i = 0; $i < $n; $i++) {
if ($nums[$i] != $i + 1) {
return $i + 1;
}
}
return $n + 1;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Cyclic Sort | Time Complexity: O(n) |
| Hash Concept with Array | Time Complexity: O(n) |
| In-place Swap | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting | O(n log n) | O(1) | Quick baseline solution when optimal constraints are not required |
| Hash Concept with Array | O(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 |
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.