First Missing Positive

🎯

First Missing Positive

hardCYCLIC_SORTAmazonFacebookGoogle

Imagine you have a list of employee ID badges, but some are missing. You want to find the smallest positive ID number that hasn't been assigned yet.

💡 This problem is about finding the smallest positive integer missing from an unsorted array. Beginners often struggle because the naive solutions are inefficient, and the optimal solution requires understanding how to rearrange elements in-place using their values as indices.

📋

Problem Statement

Given an unsorted integer array nums, find the smallest missing positive integer. Return the smallest positive integer that does not appear in nums.

1 ≤ nums.length ≤ 10^5-2^31 ≤ nums[i] ≤ 2^31 - 1

💡

Example

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

Output2

The numbers 1 and 3 and 4 are present, but 2 is missing and is the smallest positive missing integer.

Input"[1, 2, 0]"

Output3

1 and 2 are present, so the smallest missing positive integer is 3.

• All negative numbers → 1
• Array with all consecutive positive numbers starting from 1 → next integer after max
• Array with duplicates → smallest missing positive still found correctly
• Array with single element → if positive 1 missing else 1

⚠️

Common Mistakes

Not checking if nums[i] is already at correct position before swapping

Infinite loop or incorrect swaps

✅ Add condition nums[nums[i]-1] != nums[i] before swapping

Ignoring numbers out of range [1, n]

Incorrect swaps or index out of bounds errors

✅ Only swap if nums[i] is between 1 and n inclusive

Returning the wrong index + 1 after rearrangement

Wrong missing positive returned

✅ Return i+1 where nums[i] != i+1

Using sorting approach but forgetting to handle duplicates properly

May incorrectly increment missing positive

✅ Only increment missing if num == missing and skip duplicates

Using brute force with 'i not in nums' check on large arrays

Time limit exceeded due to O(n^2) complexity

✅ Avoid brute force for large inputs; use optimal approach

🧠

Brute Force (Check from 1 upwards)

💡 This approach exists to build intuition by directly checking each positive integer starting from 1 to see if it is in the array. It is simple but inefficient, helping beginners understand the problem's requirements.

Intuition

Start from 1 and check if it exists in the array. If yes, check 2, then 3, and so on until you find a number missing from the array.

Algorithm

1. Start from integer 1.
2. Check if 1 is in the array.
3. If yes, increment to 2 and check again.
4. Repeat until you find a number not in the array, then return it.

💡 This algorithm is easy to understand but requires scanning the entire array multiple times, which is inefficient.

</>

Code

def firstMissingPositive(nums):
    i = 1
    while True:
        if i not in nums:
            return i
        i += 1

# Driver code
if __name__ == '__main__':
    print(firstMissingPositive([3,4,-1,1]))  # Output: 2
    print(firstMissingPositive([1,2,0]))     # Output: 3

Line Notes

i = 1Start checking from the smallest positive integer to find the missing one

while True:Loop indefinitely until the missing positive integer is found

if i not in nums:Check if the current integer i is missing in the array

return iReturn the first missing positive integer found

import java.util.*;
public class Solution {
    public static int firstMissingPositive(int[] nums) {
        int i = 1;
        while (true) {
            boolean found = false;
            for (int num : nums) {
                if (num == i) {
                    found = true;
                    break;
                }
            }
            if (!found) return i;
            i++;
        }
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{3,4,-1,1})); // 2
        System.out.println(firstMissingPositive(new int[]{1,2,0}));    // 3
    }
}

Line Notes

int i = 1;Initialize the candidate missing positive integer starting from 1

while (true)Loop until the missing positive integer is found

for (int num : nums)Check each number in the array for presence of i

if (!found) return i;Return i if it is not found in the array

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

int firstMissingPositive(vector<int>& nums) {
    int i = 1;
    while (true) {
        bool found = false;
        for (int num : nums) {
            if (num == i) {
                found = true;
                break;
            }
        }
        if (!found) return i;
        i++;
    }
}

int main() {
    vector<int> nums1 = {3,4,-1,1};
    vector<int> nums2 = {1,2,0};
    cout << firstMissingPositive(nums1) << endl; // 2
    cout << firstMissingPositive(nums2) << endl; // 3
    return 0;
}

Line Notes

int i = 1;Start checking from the smallest positive integer to find the missing one

while (true)Infinite loop until the missing positive integer is found

for (int num : nums)Scan array to check if i exists

if (!found) return i;Return i if not found in array

function firstMissingPositive(nums) {
    let i = 1;
    while (true) {
        if (!nums.includes(i)) {
            return i;
        }
        i++;
    }
}

// Test cases
console.log(firstMissingPositive([3,4,-1,1])); // 2
console.log(firstMissingPositive([1,2,0]));    // 3

Line Notes

let i = 1;Initialize the candidate missing positive integer starting from 1

while (true)Loop until missing positive integer is found

if (!nums.includes(i))Check if i is missing in the array

return i;Return the first missing positive integer found

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each positive integer starting from 1, we scan the entire array to check presence, leading to O(n) checks repeated up to O(n) times in worst case.

💡 For n=20, this means up to 400 operations, which is inefficient for large arrays.

Interview Verdict: TLE

This approach is too slow for large inputs and will time out in interviews, but it helps understand the problem requirements.

🧠

Sorting and Linear Scan

💡 Sorting the array helps bring order, making it easier to find the missing positive by scanning once. This approach is better than brute force but still not optimal due to sorting overhead.

Intuition

Sort the array, then scan from the smallest positive number upwards to find the first missing positive integer.

Algorithm

1. Sort the array.
2. Initialize a variable to track the smallest missing positive, starting at 1.
3. Iterate through the sorted array.
4. If the current number equals the tracking variable, increment the tracking variable.
5. Return the tracking variable after iteration.

💡 Sorting simplifies the problem by ordering elements, making it easier to detect gaps.

</>

Code

def firstMissingPositive(nums):
    nums.sort()
    missing = 1
    for num in nums:
        if num == missing:
            missing += 1
        elif num > missing:
            # Skip duplicates and numbers less than missing
            continue
    return missing

# Driver code
if __name__ == '__main__':
    print(firstMissingPositive([3,4,-1,1]))  # Output: 2
    print(firstMissingPositive([1,2,0]))     # Output: 3

Line Notes

nums.sort()Sort the array to bring order and make scanning easier

missing = 1Start checking from the smallest positive integer

for num in nums:Iterate through the sorted array to find the missing positive

if num == missing:If current number matches missing, increment missing to find next candidate

import java.util.*;
public class Solution {
    public static int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int missing = 1;
        for (int num : nums) {
            if (num == missing) {
                missing++;
            } else if (num > missing) {
                // Skip duplicates and numbers less than missing
                continue;
            }
        }
        return missing;
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{3,4,-1,1})); // 2
        System.out.println(firstMissingPositive(new int[]{1,2,0}));    // 3
    }
}

Line Notes

Arrays.sort(nums);Sort the array to order elements for easier scanning

int missing = 1;Initialize missing positive tracker starting from 1

for (int num : nums)Scan through the sorted array to find missing positive

if (num == missing) missing++;Increment missing if current number matches it, skipping duplicates

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int firstMissingPositive(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int missing = 1;
    for (int num : nums) {
        if (num == missing) missing++;
        else if (num > missing) continue; // skip duplicates and smaller numbers
    }
    return missing;
}

int main() {
    vector<int> nums1 = {3,4,-1,1};
    vector<int> nums2 = {1,2,0};
    cout << firstMissingPositive(nums1) << endl; // 2
    cout << firstMissingPositive(nums2) << endl; // 3
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to arrange elements in ascending order

int missing = 1;Start from the smallest positive integer

for (int num : nums)Iterate through sorted array to find missing positive

if (num == missing) missing++;Increment missing if current number matches it, avoiding duplicates

function firstMissingPositive(nums) {
    nums.sort((a,b) => a - b);
    let missing = 1;
    for (let num of nums) {
        if (num === missing) missing++;
        else if (num > missing) continue; // skip duplicates and smaller numbers
    }
    return missing;
}

// Test cases
console.log(firstMissingPositive([3,4,-1,1])); // 2
console.log(firstMissingPositive([1,2,0]));    // 3

Line Notes

nums.sort((a,b) => a - b);Sort array numerically in ascending order

let missing = 1;Initialize missing positive tracker starting from 1

for (let num of nums)Iterate through sorted array to find missing positive

if (num === missing) missing++;Increment missing if current number matches it, skipping duplicates

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(log n) depending on sorting implementation

Sorting takes O(n log n), then a single pass O(n) to find missing positive. The sorting dominates the time complexity.

💡 For n=20, sorting takes about 86 operations, much better than brute force's 400 operations.

Interview Verdict: Accepted but not optimal

This approach passes but is slower than the optimal O(n) solution, so interviewers expect better.

🧠

Optimal Cyclic Sort / Index Placement

💡 This approach uses the idea that the smallest missing positive integer must be in the range 1 to n+1. By placing each number in its correct index (value - 1), we can find the first index where the number is incorrect, revealing the missing positive.

Intuition

Place each positive number x at index x-1 if possible. Then the first index i where nums[i] != i+1 is the missing positive integer.

Algorithm

1. Iterate through the array.
2. For each number nums[i], while it is in the range [1, n] and not at its correct position, swap it with the number at its target position nums[nums[i]-1].
3. After rearrangement, iterate again to find the first index i where nums[i] != i+1.
4. Return i+1 as the smallest missing positive integer.

💡 The key is to place numbers in their correct indices to detect the missing number by the first mismatch.

</>

Code

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= 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

# Driver code
if __name__ == '__main__':
    print(firstMissingPositive([3,4,-1,1]))  # Output: 2
    print(firstMissingPositive([1,2,0]))     # Output: 3

Line Notes

n = len(nums)Store length for boundary checks to avoid index errors

for i in range(n)Iterate over each element to place it in the correct position

while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]Swap until current number is at correct index or invalid

nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]Place number at its correct index by swapping

public class Solution {
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && 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) {
        System.out.println(firstMissingPositive(new int[]{3,4,-1,1})); // 2
        System.out.println(firstMissingPositive(new int[]{1,2,0}));    // 3
    }
}

Line Notes

int n = nums.length;Store array length for bounds checking

for (int i = 0; i < n; i++)Iterate over array to place elements correctly

while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])Swap until element is at correct position or invalid

int temp = nums[nums[i] - 1];Temporary variable for swapping elements

#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] >= 1 && 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> nums1 = {3,4,-1,1};
    vector<int> nums2 = {1,2,0};
    cout << firstMissingPositive(nums1) << endl; // 2
    cout << firstMissingPositive(nums2) << endl; // 3
    return 0;
}

Line Notes

int n = nums.size();Store array size for bounds checking

for (int i = 0; i < n; i++)Iterate over array to place elements correctly

while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])Swap until element is at correct position or invalid

swap(nums[i], nums[nums[i] - 1]);Swap elements to place them correctly

function firstMissingPositive(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            let temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }
    return n + 1;
}

// Test cases
console.log(firstMissingPositive([3,4,-1,1])); // 2
console.log(firstMissingPositive([1,2,0]));    // 3

Line Notes

const n = nums.length;Store array length for bounds checking

for (let i = 0; i < n; i++)Iterate over array to place elements correctly

while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i])Swap until element is at correct position or invalid

let temp = nums[nums[i] - 1];Temporary variable for swapping elements

⏱

Complexity

TimeO(n)

SpaceO(1)

Each number is swapped at most once to its correct position, so total operations are linear in the size of the array.

💡 For n=20, this means about 20 swaps and scans, making it very efficient compared to other approaches.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the optimal cyclic sort approach. Mention brute force and sorting to show understanding but avoid coding them due to inefficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Sorting and Linear Scan	O(n log n)	O(1) or O(log n)	No	N/A	Mention as improvement, but not optimal
3. Optimal Cyclic Sort	O(n)	O(1)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, improve to sorting, and finally present the optimal cyclic sort approach.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach and its inefficiency.Step 3: Explain sorting and linear scan as a better approach.Step 4: Present the optimal cyclic sort approach with in-place swaps.Step 5: Code the optimal solution and test edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewers test your understanding of array manipulation, in-place algorithms, and ability to optimize from naive to optimal solutions.

Common Follow-ups

• What if duplicates are present? → The cyclic sort handles duplicates by checking before swapping.
• Can you solve it without modifying the input array? → Use extra space like a hash set, but that increases space complexity.

💡 These follow-ups test your ability to handle duplicates and constraints on space usage.

🔍

Pattern Recognition

When to Use

1) Need to find missing or misplaced numbers; 2) Array contains numbers in range 1 to n; 3) In-place rearrangement possible; 4) Looking for first mismatch

Signature Phrases

smallest missing positiveunsorted arrayin-place rearrangementindex as value

NOT This Pattern When

Problems requiring sorting for order statistics or binary search on sorted arrays

Similar Problems

Find All Numbers Disappeared in an Array - similar cyclic sort rearrangementMissing Number - simpler version with one missing numberFirst Missing Positive with Duplicates - extension handling duplicates

Practice

1. You are given an array of integers where each integer is between 1 and n (inclusive), and some elements appear twice while others appear once. Which algorithmic approach guarantees finding all duplicate elements in O(n) time and O(1) extra space?

easy

A. Cyclic sort to place each number at its correct index, then scanning for mismatches

B. Using a hash set to track seen elements and identify duplicates

C. Sorting the array and then scanning for consecutive duplicates

D. Applying a dynamic programming approach to count occurrences

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 1 to n, allowing index-based placement.

2. Step 2: Identify approach that uses in-place swaps

   Cyclic sort places each number at index = number - 1, enabling O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cyclic sort exploits value-index mapping for optimal duplicate detection [OK]

Hint: Use cyclic sort for O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is always O(n) time
• Believing hash sets use O(1) space
• Confusing DP applicability for duplicates

2. Given the following code snippet implementing the cyclic sort approach, what is the returned output when the input array is [2, 2, 3]?

easy

A. [2, 1]

B. [2, 1]

C. [2, 1]

D. [2, 1]

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [2, 2, 3]. i=0, nums[0]=2, correct_index=1. nums[0] == nums[1], so increment i to 1. i=1, nums[1]=2, correct_index=1, same index, increment i to 2. i=2, nums[2]=3, correct_index=2, correct place, increment i to 3.

2. Step 2: Identify mismatch in final array

   Final array remains [2, 2, 3]. Check indices: i=0 expects 1 but has 2 (duplicate), i=1 expects 2 and has 2 (correct), i=2 expects 3 and has 3 (correct). The mismatch at i=0 means duplicate=2, missing=1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected corrupt pair [2, 1] [OK]

Hint: Trace swaps carefully; duplicates cause no swap but increment index [OK]

Common Mistakes:

• Off-by-one in indexing
• Returning wrong pair order
• Missing increment after swap

3. Consider the following Python function that finds the first k missing positive numbers using cyclic sort and a boolean array. What is the output of find_k_missing_numbers([3, -1, 4, 5, 5], 3)?

easy

A. [2, 3, 6]

B. [1, 2, 3]

C. [1, 4, 6]

D. [1, 2, 6]

Solution

1. Step 1: Perform cyclic sort on input [3, -1, 4, 5, 5]

   After sorting, the array becomes [1, -1, 3, 4, 5] with 1 at index 0, -1 at index 1, 3 at index 2, 4 at index 3, and 5 at index 4. Negative numbers are ignored in placement.

2. Step 2: Identify missing numbers and extras

   Missing numbers are 2 (since index 1 != 2), and since k=3, the next missing number beyond array length is 6. So missing = [1, 2, 6].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected missing positives [OK]

Hint: Cyclic sort places numbers correctly; missing are indices not matching values [OK]

Common Mistakes:

• Confusing indices and values after cyclic sort
• Forgetting to add missing numbers beyond array length
• Miscounting duplicates as missing

4. Identify the bug in the following code snippet that attempts to find duplicates using cyclic sort:

medium

A. Line with duplicates.append(nums[i]) repeated twice causing duplicates in output

B. Line calculating correct_index = nums[i] - 1 is off by one

C. Condition if nums[i] != nums[correct_index] should be reversed

D. Incrementing i inside else block causes infinite loop

Solution

1. Step 1: Inspect duplicate appending loop

   Duplicates were appended twice for each mismatch, causing repeated entries. The bug is fixed by removing the repeated append.

2. Step 2: Confirm other lines are correct

   Index calculation and swap condition are correct; incrementing i is proper to avoid infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicate elements appear twice in output due to repeated append [OK]

Hint: Check for repeated append calls causing duplicate outputs [OK]

Common Mistakes:

• Infinite loop due to missing i increment
• Off-by-one errors in index calculation
• Incorrect swap condition reversing logic

5. What is the time complexity of the optimal cyclic sort approach for finding the smallest missing positive range in an array of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n log n) because of the sorting-like swaps performed

B. O(n) because each element is swapped at most once to its correct position

C. O(n^2) because nested loops cause repeated scanning

D. O(n) but with O(n) auxiliary space due to recursion stack

Solution

1. Step 1: Analyze the swapping behavior

   Each element is swapped at most once to its correct index, so total swaps ≤ n.

2. Step 2: Understand loop iterations

   The outer while loop increments i only when no swap occurs, ensuring linear total iterations.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time due to bounded swaps and single pass [OK]

Hint: Each element moves at most once -> O(n) time [OK]

Common Mistakes:

• Assuming swaps cause O(n^2)
• Confusing sorting complexity with cyclic sort