First Missing Positive

Problem Statement

Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Two hard constraints

• O(n) time rules out sorting (O(n log n))
• O(1) space rules out a hash set
• The trick: use the input array itself as the hash table — it has n slots and the answer is in [1, n+1]

Examples

Input	Output	Why
[1,2,0]	3	1 and 2 present, 3 missing
[3,4,-1,1]	2	1 present, 2 missing
[7,8,9,11,12]	1	1 missing immediately

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1

Real-World Applications

Where this pattern appears

• ID gap detection — find the first unused user/order/ticket ID in a dense sequence
• Memory page allocation — find the first unallocated page frame number
• Port assignment — find the first unused network port in a range
• Sequence reconstruction — find the first missing term in a recorded integer sequence

Complexity Comparison

Approach	Time	Space	Notes
Index as Hash	O(n)	O(1)	Uses negative marking; modifies input
Cycle Sort	O(n)	O(1)	Places elements at correct positions
Hash Set (not allowed)	O(n)	O(n)	Conceptually simple but violates constraint

Approach 1: Index as Hash (Recommended)

★ Recommended

⏱ Time O(n) Three linear passes 💾 Space O(1) In-place marking

The key insight: the answer must be in the range [1, n+1]. This means the array’s n slots are exactly enough to encode presence of every candidate value. We use negative sign as a boolean flag at the index corresponding to each value.

Three phases:

1. Clean: replace irrelevant values (≤0 or >n) with n+1 so they don’t interfere with marking
2. Mark: for each value v = abs(nums[i]) where 1 ≤ v ≤ n, negate nums[v-1] to mark “v is present”
3. Scan: find first index i where nums[i] > 0 → return i+1

Step-by-step Example

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

Phase 1 — replace -1 (≤0) with n+1=5: [3,4,5,1]

Phase 2 — mark:

i	abs(nums[i])	mark index	array after
0	3	2	[3,4,-5,1]
1	4	3	[3,4,-5,-1]
2	5 > n	skip	[3,4,-5,-1]
3	1	0	[-3,4,-5,-1]

Phase 3 — scan [-3,4,-5,-1]: index 1 has positive 4 → return 2 ✓

Animated walkthrough

Index-as-Hash marking phase on [3,4,-1,1]

Watch how each value's presence is encoded by negating the slot at index (value-1). Use Next or Autoplay.

Back Autoplay Next Reset

Step 1 of 6

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function firstMissingPositive(nums):
    n = len(nums)
    # Phase 1: replace non-positives and > n
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1
    # Phase 2: mark presence
    for i in range(n):
        v = abs(nums[i])
        if 1 <= v <= n:
            nums[v-1] = -abs(nums[v-1])
    # Phase 3: find first unmarked
    for i in range(n):
        if nums[i] > 0:
            return i + 1
    return n + 1

Solution Code

Python

first_missing_positive_index_hash.py

from typing import List


def first_missing_positive(nums: List[int]) -> int:
    n = len(nums)

    # Phase 1: replace non-positives and values > n with n+1
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1

    # Phase 2: mark presence using negative signs
    for i in range(n):
        v = abs(nums[i])
        if 1 <= v <= n:
            nums[v - 1] = -abs(nums[v - 1])

    # Phase 3: find first unmarked index
    for i in range(n):
        if nums[i] > 0:
            return i + 1

    return n + 1


print(first_missing_positive([1, 2, 0]))        # 3
print(first_missing_positive([3, 4, -1, 1]))    # 2
print(first_missing_positive([7, 8, 9, 11, 12]))  # 1

C++

first_missing_positive_index_hash.cpp

#include <cmath>
#include <vector>
using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        // Phase 1: replace non-positives and values > n with n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // Phase 2: mark presence using negative signs
        for (int i = 0; i < n; i++) {
            int v = abs(nums[i]);
            if (v >= 1 && v <= n) {
                nums[v - 1] = -abs(nums[v - 1]);
            }
        }

        // Phase 3: find first unmarked index
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }
};

Java

first_missing_positive_index_hash.java

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Phase 1: replace non-positives and values > n with n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // Phase 2: mark presence using negative signs
        for (int i = 0; i < n; i++) {
            int v = Math.abs(nums[i]);
            if (v >= 1 && v <= n) {
                nums[v - 1] = -Math.abs(nums[v - 1]);
            }
        }

        // Phase 3: find first unmarked index
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }
}

JavaScript

first_missing_positive_index_hash.js

/**
 * @param {number[]} nums
 * @return {number}
 */
function firstMissingPositive(nums) {
    const n = nums.length;

    // Phase 1: replace non-positives and values > n with n+1
    for (let i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = n + 1;
        }
    }

    // Phase 2: mark presence using negative signs
    for (let i = 0; i < n; i++) {
        const v = Math.abs(nums[i]);
        if (v >= 1 && v <= n) {
            nums[v - 1] = -Math.abs(nums[v - 1]);
        }
    }

    // Phase 3: find first unmarked index
    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }

    return n + 1;
}

Rust

first_missing_positive_index_hash.rs

impl Solution {
    pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;

        // Phase 1: replace non-positives and values > n with n+1
        for i in 0..nums.len() {
            if nums[i] <= 0 || nums[i] > n {
                nums[i] = n + 1;
            }
        }

        // Phase 2: mark presence using negative signs
        for i in 0..nums.len() {
            let v = nums[i].abs();
            if v >= 1 && v <= n {
                let idx = (v - 1) as usize;
                let cur = nums[idx].abs();
                nums[idx] = -cur;
            }
        }

        // Phase 3: find first unmarked index
        for i in 0..nums.len() {
            if nums[i] > 0 {
                return (i as i32) + 1;
            }
        }

        n + 1
    }
}

Go

first_missing_positive_index_hash.go

package golang

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

  // Phase 1: replace non-positives and values > n with n+1
  for i := 0; i < n; i++ {
    if nums[i] <= 0 || nums[i] > n {
      nums[i] = n + 1
    }
  }

  // Phase 2: mark presence using negative signs
  for i := 0; i < n; i++ {
    v := nums[i]
    if v < 0 {
      v = -v
    }
    if v >= 1 && v <= n {
      if nums[v-1] > 0 {
        nums[v-1] = -nums[v-1]
      }
    }
  }

  // Phase 3: find first unmarked index
  for i := 0; i < n; i++ {
    if nums[i] > 0 {
      return i + 1
    }
  }

  return n + 1
}

Approach 2: Cycle Sort

🎯 Interview Favourite

⏱ Time O(n) Each element moved at most once 💾 Space O(1) In-place

Place each number at its “correct” position: value v belongs at index v-1. Keep swapping until every element is either in its correct slot or out of range. Then scan for the first mismatch.

Step-by-step Example

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

i	nums[i]	correct idx	action	array
0	3	2	swap(0,2)	[-1,4,3,1]
0	-1	invalid	skip	[-1,4,3,1]
1	4	3	swap(1,3)	[-1,1,3,4]
1	1	0	swap(1,0)	[1,-1,3,4]
1	-1	invalid	skip	[1,-1,3,4]
2	3	2 ✓	skip	[1,-1,3,4]
3	4	3 ✓	skip	[1,-1,3,4]

Scan: index 0: nums[0]=1=1 ✓, index 1: nums[1]=-1≠2 → return 2 ✓

Pseudocode

function firstMissingPositive(nums):
    n = len(nums)
    i = 0
    while i < n:
        j = nums[i] - 1  # correct index for nums[i]
        if 1 <= nums[i] <= n and nums[j] != nums[i]:
            swap(nums[i], nums[j])
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Solution Code

Python

first_missing_positive_cycle_sort.py

from typing import List


def first_missing_positive(nums: List[int]) -> int:
    n = len(nums)
    i = 0

    # Place each number at its correct index (value v at index v-1)
    while i < n:
        j = nums[i] - 1
        if 1 <= nums[i] <= n and nums[j] != nums[i]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1

    # Find first index where value doesn't match expected
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1


print(first_missing_positive([1, 2, 0]))        # 3
print(first_missing_positive([3, 4, -1, 1]))    # 2
print(first_missing_positive([7, 8, 9, 11, 12]))  # 1

C++

first_missing_positive_cycle_sort.cpp

#include <vector>
using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        int i = 0;

        // Place each number at its correct index (value v at index v-1)
        while (i < n) {
            int j = nums[i] - 1;
            if (nums[i] >= 1 && nums[i] <= n && nums[j] != nums[i]) {
                swap(nums[i], nums[j]);
            } else {
                i++;
            }
        }

        // Find first index where value doesn't match expected
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};

Java

first_missing_positive_cycle_sort.java

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int i = 0;

        // Place each number at its correct index (value v at index v-1)
        while (i < n) {
            int j = nums[i] - 1;
            if (nums[i] >= 1 && nums[i] <= n && nums[j] != nums[i]) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            } else {
                i++;
            }
        }

        // Find first index where value doesn't match expected
        for (int k = 0; k < n; k++) {
            if (nums[k] != k + 1) {
                return k + 1;
            }
        }

        return n + 1;
    }
}

JavaScript

first_missing_positive_cycle_sort.js

/**
 * @param {number[]} nums
 * @return {number}
 */
function firstMissingPositive(nums) {
    const n = nums.length;
    let i = 0;

    // Place each number at its correct index (value v at index v-1)
    while (i < n) {
        const j = nums[i] - 1;
        if (nums[i] >= 1 && nums[i] <= n && nums[j] !== nums[i]) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
        } else {
            i++;
        }
    }

    // Find first index where value doesn't match expected
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }

    return n + 1;
}

Rust

first_missing_positive_cycle_sort.rs

impl Solution {
    pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut i = 0;

        // Place each number at its correct index (value v at index v-1)
        while i < n {
            let j = (nums[i] - 1) as usize;
            if nums[i] >= 1 && nums[i] <= n as i32 && nums[j] != nums[i] {
                nums.swap(i, j);
            } else {
                i += 1;
            }
        }

        // Find first index where value doesn't match expected
        for i in 0..n {
            if nums[i] != (i as i32) + 1 {
                return (i as i32) + 1;
            }
        }

        (n as i32) + 1
    }
}

Go

first_missing_positive_cycle_sort.go

package golang

func firstMissingPositiveCycleSort(nums []int) int {
  n := len(nums)
  i := 0

  // Place each number at its correct index (value v at index v-1)
  for i < n {
    j := nums[i] - 1
    if nums[i] >= 1 && nums[i] <= n && nums[j] != nums[i] {
      nums[i], nums[j] = nums[j], nums[i]
    } else {
      i++
    }
  }

  // Find first index where value doesn't match expected
  for i := 0; i < n; i++ {
    if nums[i] != i+1 {
      return i + 1
    }
  }

  return n + 1
}

Common mistakes

• Index-as-hash — skipping Phase 1: negatives in the array would cause abs() to produce indices pointing at wrong slots or out-of-range indices
• Cycle sort — infinite loop on duplicates: if nums[i] == nums[nums[i]-1], swapping loops forever — always guard with nums[j] != nums[i] before swapping
• Off-by-one: value v belongs at index v-1, not v

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

first_missing_positive_space_optimized.py

"""
Solution for First Missing Positive
"""

def solve():
    """Implementation for approach 3 of First Missing Positive"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

first_missing_positive_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for First Missing Positive
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

FirstMissingPositiveSpaceOptimized.java

/**
 * Solution for First Missing Positive
 * Approach 3
 */
public class FirstMissingPositiveSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

first_missing_positive_space_optimized.js

/**
 * Solution for First Missing Positive
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

first_missing_positive_space_optimized.rs

/// Solution for First Missing Positive
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

first_missing_positive_space_optimized.go

package main

import "fmt"

// Solution for First Missing Positive
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Missing Number ↗ Easy #268
• Find the Duplicate Number ↗ Medium #287
• Longest Consecutive Sequence ↗ Medium #128

Interview Tips

Key points to cover

• State both constraints up front (O(n) time, O(1) space) — they together rule out sorting and hash sets
• The answer MUST be in [1, n+1] — use this bound to justify using the array as storage
• The index-as-hash approach is more commonly expected; cycle sort is a nice variant to mention
• For index-as-hash, emphasize that abs() in Phase 2 is necessary because earlier iterations may have already negated the value

← Previous
#39 Combination Sum Next
#42 Trapping Rain Water →