First Missing Positive Integer — Problem Statement & Solution Guide

ArraysMediumMixed

TimeO(n)

SpaceO(1)

Problem Description

You are provided with an unsorted array of integers nums and an integer k. The goal is to identify the smallest positive integer x such that 1 <= x <= k and x does not appear in nums.

It is guaranteed that at least one such integer exists within the range [1, k]. Note that integers in nums may be negative, zero, or greater than k, and duplicates are permitted. Your solution should efficiently determine the first missing value without necessarily sorting the entire array, leveraging the constraints to optimize time and space complexity.

DSA Pattern Breakdown

"First Missing Positive Integer"

medium

WHY DOES IT MATTER?

In‑place indexing transforms the input array into a constant‑space hash map, a pattern that appears in many "first missing" or "duplicate detection" problems. Mastering it shows you can squeeze optimal time and space out of constrained environments—a skill highly valued in system design and performance‑critical code.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that the array index itself can serve as the hash bucket for values in a bounded range. By swapping elements until each valid value lands at its bucket, you eliminate the need for auxiliary data structures and achieve linear time.

REAL-WORLD CONNECTION

Think of a distributed key‑value store that shards data based on a hash of the key. By placing each key in its designated shard (index), you can quickly detect missing shards (holes) without scanning the entire keyspace or maintaining a separate index structure.

During the interview, write the swap loop as a while‑inside‑for construct and explicitly check the three guard conditions (range, correct position, and duplicate) before swapping. This prevents infinite loops and makes your intent crystal clear to the interviewer.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem is a variant of the classic "first missing positive" challenge, which can be solved in linear time using in‑place indexing (also known as cyclic sort). The key insight is that any integer x in the range [1, k] can be placed at index x‑1, turning the array itself into a hash table without extra memory. By repeatedly swapping elements into their correct positions, we guarantee that after one pass each index either holds its rightful value or an out‑of‑range/duplicate value. A subsequent linear scan then reveals the smallest index i where nums[i] ≠ i+1, and i+1 is the answer. Naïve solutions—such as sorting the array (O(n log n)) or using a hash set (O(n) time but O(n) extra space)—either exceed the time budget for massive inputs or violate the O(1) auxiliary space constraint that interviewers often enforce for this pattern. The optimal paradigm leverages the fact that the array length n bounds the number of distinct candidates we need to consider, allowing us to achieve O(n) time and O(1) extra space by mutating the input in‑place.

Interview Questions on This Problem

Q1How would you modify the in‑place algorithm if the array length n is smaller than k, but you still need to guarantee O(1) extra space?

You only need to consider the first n positions because you can place at most n distinct numbers in the range [1, k]. After the cyclic placement, scan indices 0..n‑1; the first i where nums[i] ≠ i+1 gives the missing value. If all positions are correct, the answer is n+1 (which is ≤ k by problem guarantee). No extra storage beyond a few variables is required.

Q2Why does the cyclic‑sort technique fail if you try to place numbers larger than the array size, and how do you guard against it?

Swapping a value > n (or > k) into index value‑1 would cause an out‑of‑bounds access. The algorithm therefore includes a guard: only attempt a swap when the current value v satisfies 1 ≤ v ≤ min(n, k) and nums[v‑1] ≠ v. Values outside this range are left untouched, effectively acting as placeholders for missing numbers.

Q3Can you extend this solution to find the first missing positive in a read‑only array? What would be the trade‑off?

In a read‑only scenario you cannot mutate the input, so the O(1) space in‑place trick is unavailable. You would fall back to using a bitset or hash set, which costs O(n) extra space but still runs in O(n) time. The trade‑off is higher memory usage, which may be acceptable if the array size fits within available RAM.

Examples

Example 1

Input

nums = [2, 3, 1, 4], k = 4

Output

Explanation: The range of interest is [1, 4]. The array contains 1, 2, 3, and 4. Since all integers in the range [1, 4] are present, the first missing positive integer within the specified bound is 5.

Example 2

Input

nums = [1, 2, 4], k = 5

Output

Explanation: The range of interest is [1, 5]. The array contains 1, 2, and 4. The integer 3 is missing from the array. Therefore, 3 is the first missing positive integer.

Example 3

Input

nums = [5, 6, 7], k = 3

Output

Explanation: The range of interest is [1, 3]. The array contains 5, 6, and 7, none of which fall within [1, 3]. The smallest positive integer in the range is 1, which is missing. Thus, the answer is 1.

Example 4

Input

nums = [1, 1, 2, 3], k = 4

Output

Explanation: The range of interest is [1, 4]. The array contains 1 (twice), 2, and 3. The integer 4 is not present in the array. Hence, 4 is the first missing positive integer.

Constraints

1 <= nums.length <= 10^5
1 <= k <= 10^5
-10^9 <= nums[i] <= 10^9
The answer is guaranteed to be within the range [1, k+1]

Optimal Approach & Strategy

Perform an in‑place cyclic sort that places each value v (1 ≤ v ≤ min(n, k)) at index v‑1, then scan for the first index i where nums[i] ≠ i+1; i+1 is the answer.

Brute Force Approach

Use a hash set to store all numbers in [1, k] that appear in the array, then iterate from 1 to k and return the first integer not in the set.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var firstMissingPositive = function(nums, k) {
    const seen = new Set(nums);
    for (let i = 1; i <= k; i++) {
        if (!seen.has(i)) {
            return i;
        }
    }
    return k + 1;
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums, int k) {
        unordered_set<int> seen(nums.begin(), nums.end());
        for (int i = 1; i <= k; ++i) {
            if (seen.find(i) == seen.end()) {
                return i;
            }
        }
        return k + 1;
    }
};

class Solution {
    public int firstMissingPositive(int[] nums, int k) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            seen.add(num);
        }
        for (int i = 1; i <= k; i++) {
            if (!seen.contains(i)) {
                return i;
            }
        }
        return k + 1;
    }
}

class Solution:
    def firstMissingPositive(self, nums: List[int], k: int) -> int:
        seen = set(nums)
        for i in range(1, k + 1):
            if i not in seen:
                return i
        return k + 1

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var firstMissingPositive = function(nums, k) {
    const seen = new Set(nums);
    for (let i = 1; i <= k; i++) {
        if (!seen.has(i)) {
            return i;
        }
    }
    return k + 1;
};

Asked in Top Tech Interviews

arraysmediumgeneric

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

First Missing Positive Integer Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

First Missing Positive Integer — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor