Log inSign up
hardLeetCodeNot Started

First Missing Positive

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard Missing Element:

Input: nums = [1, 2, 0]
Output: 3
Explanation: The numbers in the range [1, 2] are present, so the smallest missing positive integer is 3.

Example 2 · Missing Middle Element:

Input: nums = [3, 4, -1, 1]
Output: 2
Explanation: 1 is in the array, but 2 is missing. So 2 is returned.

Example 3 · Consecutive Numbers:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Pigeonhole Principle and range bounded search
  • Cycle sort and in-place array swapping
  • Handling negative numbers and duplicates

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply the Pigeonhole Principle to bound the search range to [1, N+1].
  • Master the in-place cycle sort technique to achieve O(1) space.
  • Correctly prevent infinite loops when handling duplicate numbers.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Find All Numbers Disappeared in an ArrayFind the Duplicate NumberSet Mismatch

1. Hash Set Lookup (Brute Force)

Intuition

Add all elements to a hash set, then check for the presence of 1, 2, 3, ... up to N + 1.

Algorithm

  1. 1. Insert all numbers from nums into a HashSet.
  2. 2. Loop target from 1 to N+1: - If target not in set, return target.
  3. 3. Return N + 1.

Brute Force Successive Positive Integer Membership Scans

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [3, 4, -1, 1]
Current operationSTEP 1 OF 6
Phase 1 — 1 is present Advance candidate to 2: Step 1: Smallest positive integer is 1
Visual state
Values and pointers at this exact step
array
S
3
4
-1
1
0
1
2
3
↑ Scan for target = 1
Variables at this step
candidate
1
Found
true
Next
2
Check / comparison
Check candidate = 1: Linear scan finds 1 at nums[3].
Decision / next transition
1 is present. Advance candidate to 2.
Why this step matters

Phase 1 — 1 is present Advance candidate to 2: Step 1: Smallest positive integer is 1. Scan array for 1: found at index 3. Increment candidate to 2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4using namespace std;
5
6// Brute Force Approach: Hash Set Lookup
7int firstMissingPositive(const vector<int>& nums) {
8 unordered_set<int> seen(nums.begin(), nums.end());
9 int n = nums.size();
10 for (int i = 1; i <= n + 1; i++) {
11 if (seen.find(i) == seen.end()) {
12 return i;
13 }
14 }
15 return n + 1;
16}
17
18int main() {
19 vector<int> nums = {3, 4, -1, 1};
20 int result = firstMissingPositive(nums);
21 cout << "Output: " << result << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N) — Inserting N items takes O(N). Checking 1..N+1 takes at most N+1 lookups of O(1) each.
  • Space complexity: O(N) — Hash set requires O(N) auxiliary memory.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Sort and Linear Scan (Better)

Intuition

Sort the array in-place and scan for the first expected positive number.

Algorithm

  1. 1. Sort nums in ascending order.
  2. 2. Initialize expected = 1.
  3. 3. Loop through each x in sorted nums: - if x == expected: expected++ - else if x > expected: return expected.
  4. 4. Return expected.

Hash Set Lookup for Range [1..N+1]

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [3, 4, -1, 1]
Current operationSTEP 1 OF 6
Phase 1 — Set construction takes O(N) time and O(N) space: Step 1: Place all numbers in a hash set to enable O(1) existence lookups
Visual state
Values and pointers at this exact step
array
S
3
4
-1
1
0
↑ Build Set
1
2
3
Variables at this step
HashSet
{ 3, 4, -1, 1 }
Check / comparison
Insert all elements into Hash Set: set = { 3, 4, -1, 1 }.
Decision / next transition
Set construction takes O(N) time and O(N) space.
Why this step matters

Phase 1 — Set construction takes O(N) time and O(N) space: Step 1: Place all numbers in a hash set to enable O(1) existence lookups.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Better Approach: Sort and Linear Scan
7int firstMissingPositive(vector<int>& nums) {
8 sort(nums.begin(), nums.end());
9 int expected = 1;
10 for (int x : nums) {
11 if (x == expected) {
12 expected++;
13 } else if (x > expected) {
14 return expected;
15 }
16 }
17 return expected;
18}
19
20int main() {
21 vector<int> nums = {3, 4, -1, 1};
22 int result = firstMissingPositive(nums);
23 cout << "Output: " << result << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting takes O(N log N) time; the scan takes O(N).
  • Space complexity: O(1) — In-place sort uses O(1) auxiliary memory.

3. In-Place Cycle Swapping (Optimal)

Intuition

Place each number x in [1, N] at index (x - 1) using cyclic swaps in O(N) time and O(1) space.

Algorithm

  1. 1. Loop i from 0 to N-1: - While nums[i] >= 1 and nums[i] <= N and nums[i] != nums[nums[i] - 1]: - swap(nums[i], nums[nums[i] - 1]).
  2. 2. Loop i from 0 to N-1: - If nums[i] != i + 1, return i + 1.
  3. 3. Return N + 1.

In-Place Cyclic Sort (Value x Belongs at Index x - 1)

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [3, 4, -1, 1]
Current operationSTEP 1 OF 8
Phase 1 — Step 1: Step 1 (Cyclic Sort at Idx 0): Invariant: any value x in [1, n] belongs at index x - 1
Visual state
Values and pointers at this exact step
array
S
3
4
-1
1
0
↑ i=0: val 3
1
2
↑ Target: idx 2
3
Variables at this step
i
0
val
3
targetIdx
2
Action
Swap(0, 2)
nums
[-1, 4, 3, 1]
Check / comparison
nums[0] = 3 is in range [1, 4]. Belongs at target index 3 - 1 = 2! nums[2] = -1 != 3.
Decision / next transition
Swap nums[0] and nums[2]! Array becomes: [-1, 4, 3, 1].
Why this step matters

Phase 1 — Step 1: Step 1 (Cyclic Sort at Idx 0): Invariant: any value x in [1, n] belongs at index x - 1. nums[0] = 3 belongs at index 2. Swap nums[0] with nums[2]. Array becomes [-1, 4, 3, 1].

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Optimal Approach: In-Place Cycle Swapping
7int firstMissingPositive(vector<int>& nums) {
8 int n = nums.size();
9 for (int i = 0; i < n; i++) {
10 while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
11 swap(nums[i], nums[nums[i] - 1]);
12 }
13 }
14 for (int i = 0; i < n; i++) {
15 if (nums[i] != i + 1) {
16 return i + 1;
17 }
18 }
19 return n + 1;
20}
21
22int main() {
23 vector<int> nums = {3, 4, -1, 1};
24 int result = firstMissingPositive(nums);
25 cout << "Output: " << result << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(N) — Each number is swapped into its final position at most once. Total swaps across the entire loop is bounded by N, giving O(N) amortized time.
  • Space complexity: O(1) — Swapping is performed in-place with O(1) extra variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash SetO(N)O(N)Insert all elements into a hash set, then test integers 1, 2, 3... up to N+1.Hash set memory allocation.
2.Better — SortingO(N log N)O(1) or O(N)Sort the array, then iterate looking for missing positive values starting from 1.Comparison-based sorting overhead.
3.Optimal — In-Place Cycle SwappingOptimalO(N)O(1)Place each number x into index x-1 using cyclic swaps in O(N) total steps and O(1) space.None; optimal algorithm.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Array with duplicate elements: nums = [1, 1] -> infinite loop if while condition doesn't check nums[i] != nums[nums[i]-1].
  • All negative numbers: nums = [-1, -2, -3] -> returns 1.
  • Array is already [1, 2, 3... N] -> returns N + 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for First Missing Positive?

2.Why is the brute force approach suboptimal for large inputs in First Missing Positive?

3.Which data structure or technique enables the optimal solution for First Missing Positive?

Back to DSA Sheet