2Brute2Best
🔥0

First Missing Positive

Hard·LeetCode #41 Pro OnlyTricky / Edge Case
LeetCode
01

Problem Statement

You are given an unsorted integer array nums. It can contain zeros, negative numbers, very large numbers and duplicates.

Return the smallest positive integer (1, 2, 3, …) that does not appear in nums.

Your algorithm must run in O(N) time and use only O(1) extra space.

Input

An integer array nums.

Output

The smallest positive integer missing from nums.

Example 1
Input: nums = [1, 2, 0]
Output: 3

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

Example 2
Input: nums = [3, 4, -1, 1]
Output: 2

1 is present but 2 is not.

Example 3
Input: nums = [7, 8, 9, 11, 12]
Output: 1

Even 1 is missing. The large values do not matter.

Constraints
  • • 1 ≤ nums.length ≤ 10^5
  • • −2^31 ≤ nums[i] ≤ 2^31 − 1
  • • O(N) time and O(1) extra space.
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“smallest missing positive”
→ Check 1, 2, 3, … in order — a membership question.
“O(N) time”
→ No sorting (O(N log N)), no rescanning per k.
“O(1) extra space”
→ No hash set — the array must store the membership itself.
“answer is in 1..n+1”
→ Values map to indices 0..n−1, so each value has a home slot.
03

Approach Complexity Ladder

Brute Force — check 1, 2, 3, … one by oneO(N²)O(1)

For each k from 1, scan the array to see if k is there

Better — hash set of positivesO(N)O(N)

Put positives in a set; first k in 1..n+1 not in it

Optimal — use the array as its own hash setO(N)O(1)

Swap each value v (1..n) into index v − 1, then find the first wrong slot

Brute Force Intuition

Try k = 1, then 2, then 3, … For each k, scan the whole array. The first k that is not found is the answer. We never need to go past n + 1.

Recognition rule for this sub-pattern:

Put everything in a set first; then each "is X present?" check is O(1). Start work only from the beginning of a run.
Remember this · Arrays & Hashing
Trigger
"Have I seen X before?", pairs that add up to a target, grouping things that look alike, counting occurrences.
Think
Instead of scanning again for each element, can I remember earlier elements in a map?
Key question
What exactly do I store as the key, and what as the value?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.

LLD Machine Coding

In-Memory LRU / LFU Cache

Hash map combined with doubly linked list for O(1) eviction and lookup.

Explore Track
C++ Internals

STL unordered_map Internals & Rehashing

Bucket arrays, collision chaining, load factors, and custom hash functors.

Explore Track
Longest Consecutive Sequence