In-Place Hashing Cracks LeetCode 41: O(n) Time, O(1) Space
This article explains how to solve LeetCode 41 First Missing Positive using in-place hashing, leveraging the pigeonhole principle to bound the answer, and provides two Java implementations—cyclic sort and sign marking—with detailed walkthroughs, pitfall analysis, and interview follow-up questions.
Problem: LeetCode 41 First Missing Positive
Given an unsorted integer array nums, find the smallest missing positive integer. Constraints: O(n) time and O(1) space .
Examples:
Input: [1, 2, 0] Output: 3
Input: [3, 4, -1, 1] Output: 2
Input: [7, 8, 9, 11, 12] Output: 1This high-frequency Hard question appears in interviews at companies like ByteDance and Tencent. The constraints rule out sorting (O(n log n) time) and HashSet (O(n) space), forcing an in-place solution.
Pigeonhole Principle: Answer Range [1, n+1]
The key insight: for an array of length n, the smallest missing positive must lie in [1, n+1].
Proof: n positions can hold at most n distinct positive integers. If 1 through n all appear, the answer is n+1; otherwise, the answer is in 1..n.
This compresses the infinite search space to n candidate buckets. Negative numbers, zero, and values > n are distractions and can be ignored in-place.
Why Sorting and HashSet Fail
A comparison of approaches:
Sort then scan: O(n log n) time, O(1)–O(n) space → fails time constraint.
HashSet / boolean array: O(n) time, O(n) space → fails space constraint.
In-place hashing (cyclic sort): O(n) time, O(1) space → passes.
Sign marking: O(n) time, O(1) space → passes.
The first two serve as interview warm-up; the real solution must squeeze the array itself.
Core Idea: Array as Hash Table
Value x belongs at index x-1 . Place each number in its "home" index, then scan for the first empty seat.
Index-to-value mapping:
Index 0 → value 1
Index 1 → value 2
Index 2 → value 3
…
Index n-1 → value n
Placement rules:
Only process elements where 1 <= nums[i] <= n; ignore others.
If nums[i] is not at its correct index and the target index holds a different value, swap.
After placement, scan for first nums[i] != i+1; answer is i+1. If all match, answer is n+1.
Walkthrough: [3, 4, -1, 1] Step by Step
Array length n=4. Only values 1..4 are processed.
i=0: [3,4,-1,1] → 3 belongs at index 2, swap with -1 → [-1,4,3,1]
i=0: -1 invalid, i++
i=1: [-1,4,3,1] → 4 belongs at index 3, swap with 1 → [-1,1,3,4]
i=1: swapped-in 1 belongs at index 0, swap with -1 → [1,-1,3,4]
i=1: -1 invalid, i++
i=2: 3 at index 2 (correct), i++
i=3: 4 at index 3 (correct), done.
Final scan: index 0 has 1 (match), index 1 has -1 (mismatch) → answer = 2.
Note steps 3–4: after placing 4, the incoming 1 must also be placed. This chaining requires a while loop, not if.
Java Implementation: Cyclic Sort (Primary)
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Phase 1: in-place placement
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n
&& nums[nums[i] - 1] != nums[i]) {
int targetIdx = nums[i] - 1;
int temp = nums[i];
nums[i] = nums[targetIdx];
nums[targetIdx] = temp;
}
}
// Phase 2: linear scan
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// All 1..n present
return n + 1;
}
}Critical Detail 1: while not if
The swapped-in value may also need placement. Example [3,1,2]: i=0 swaps 3 to index 2, bringing 2 to index 0; 2 must then go to index 1. if would miss the second swap.
Critical Detail 2: nums[nums[i]-1] != nums[i] prevents infinite loop
Without it, input [1,1] causes self-swap at index 0 forever. The check stops when target already holds the correct value (duplicate handled).
Critical Detail 3: Amortized O(n) despite nested loops
Each swap puts at least one element into its final position, never to be moved again. With n elements, total swaps ≤ n, so the while loop is amortized O(n), not O(n²).
Alternative: Sign Marking (No Position Changes)
Three steps:
Sanitize: replace non-positive values with sentinel n+1.
Mark: for each x = |nums[i]|, if x <= n, set nums[x-1] = -|nums[x-1]|.
Verify: first index with positive value gives answer i+1; if none, answer n+1.
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Step 1: sanitize
for (int i = 0; i < n; i++) {
if (nums[i] <= 0) nums[i] = n + 1;
}
// Step 2: mark with negative sign
for (int i = 0; i < n; i++) {
int x = Math.abs(nums[i]);
if (x <= n) {
nums[x - 1] = -Math.abs(nums[x - 1]);
}
}
// Step 3: find first positive
for (int i = 0; i < n; i++) {
if (nums[i] > 0) return i + 1;
}
return n + 1;
}
}Advantages: preserves element order. Pitfall: Math.abs(Integer.MIN_VALUE) stays negative, but sanitization confines values to [1, n+1], avoiding overflow.
Comparison: Cyclic Sort vs Sign Marking
Core action: move value to index vs. flip sign at index.
Data mutation: reorders elements vs. only changes signs.
Code shape: single while loop vs. three passes with sanitization.
Typical pitfalls: duplicate infinite loop vs. sign/abs edge cases.
Interview role: primary solution vs. backup when "no position change" required.
Seven Common Pitfalls
Using if instead of while → misses chained placements (e.g., [3,4,-1,1] fails).
Missing duplicate check → [1,1] infinite self-swap.
No range guard → negative/large values cause index out of bounds.
XOR swap → when i == targetIdx, value becomes zero.
Forgetting n+1 fallback → [1,2,3] crashes or returns wrong.
Assuming O(n²) due to nested loops → explain amortized analysis.
Math.abs(Integer.MIN_VALUE) overflow → sanitization avoids it.
Interview Follow-up Questions
Q1: All negatives? Return 1.
Q2: Perfect sequence [1,2,3,...,n]? Return n+1 (fallback covers it).
Q3: Why ignore negatives and >n? Answer range is [1,n+1]; they can't be the answer and don't affect 1..n placement.
Q4: Cannot modify array? If O(1) space + O(n) time still required → impossible. Compromises: copy + sort (O(n log n)), or BitSet (O(n) space, ~n/8 bits).
Q5: Find first k missing positives? After placement, collect indices where nums[i] != i+1; if fewer than k, append n+1, n+2, ...
Q6: Read-only array, O(n) space allowed? Use boolean[] seen = new boolean[n+1] or BitSet.
Q7: Real-world use? Distributed ID gap detection (sharded auto-increment IDs), gateway message sequence gap detection.
Test Cases for Self-Check
[] → 1
[1] → 2
[2,1] → 3
[1,1] → 2
[1,2,0] → 3
[3,4,-1,1] → 2
[7,8,9,11,12] → 1
[1,2,3] → 4
[0,-1,-2] → 1Key Takeaways
For length n, answer ∈ [1, n+1]; place each number at index x-1 using while + duplicate guard; scan for gap. Amortized O(n), O(1) space.
In one sentence: Assign each number to its slot; the first empty slot is the answer.
This pattern solves LeetCode 442 (Find All Duplicates) and 448 (Find All Numbers Disappeared) as well.
Three practical tips:
From constraints, derive answer range first—range shrinkage is often the breakthrough.
Memorize the "while + range guard + duplicate check" trio—it's the in-place hashing safety net.
Mentally run boundary cases before submitting; one minute of self-check beats live debugging.
The constraints themselves are the hint: O(1) space forces "use the array as the hash table."
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
