4
n
Find the smallest positive integer missing from an unsorted array in O(n) time and O(1) extra space. The trick: turn the array into its own hash table by sending every value v to slot v − 1, then scan for the first slot that's wrong.
Given an unsorted array, return the smallest positive integer (1, 2, 3, …) that does not appear in it. Take nums = [3,4,-1,1]. The positives present are {1, 3, 4}; 2 is missing, so the answer is 2. The catch is the constraint: do it in O(n) time and O(1) extra space, which rules out a hash set or sorting.
n is always in [1, n+1]. So value v belongs at index v − 1. Permute the array in place until every in-range value sits in its home slot; then the first index i whose value isn't i + 1 reveals the missing number i + 1.Why is the answer at most n + 1? With only n slots, the best case is that 1..n are all present, leaving n + 1. Negatives, zeros, and values > n are irrelevant — they can never be the answer, so we simply ignore them.
nums[i] is in [1, n]AND its home slot doesn't already hold it: send nums[i] to index nums[i] − 1.nums[i] is out of range or its home already holds the right value (duplicate) — then advance i.nums[i] !== i + 1; return i + 1. If none, return n + 1.while, not an if, and you must not advance i after a swap. A single swap drops a new value into nums[i] that may itself need placing. The duplicate guard nums[nums[i] − 1] !== nums[i] is what stops an infinite swap loop when the home slot already holds the same value.Each swap puts at least one value into its final home, and a value never leaves a correct home. So across the whole outer loop there are at most n swaps total — the nested while is amortized O(1) per index, keeping the phase O(n).
n = 4. The answer must be in [1, 5]. Phase 1: send each value v to slot v-1.1function firstMissingPositive(nums: number[]): number {2▶ const n = nums.length;34 // Phase 1 — place each value v in slot v-1 (cyclic sort).5▶ for (let i = 0; i < n; i++) {6 // Only swap when nums[i] is a useful, out-of-place value 1..n.7 while (8 nums[i] >= 1 &&9 nums[i] <= n &&10 nums[nums[i] - 1] !== nums[i]11 ) {12 const target = nums[i] - 1; // where nums[i] belongs13 [nums[i], nums[target]] = [nums[target], nums[i]];14 }15 }1617 // Phase 2 — first index that doesn't hold i+1 is the answer.18 for (let i = 0; i < n; i++) {19 if (nums[i] !== i + 1) return i + 1;20 }2122 // Every slot 1..n is filled, so the answer is n+1.23 return n + 1;24}
function firstMissingPositive(nums: number[]): number {
const n = nums.length;
// Phase 1 — place each value v in slot v-1 (cyclic sort).
for (let i = 0; i < n; i++) {
// Only swap when nums[i] is a useful, out-of-place value 1..n.
while (
nums[i] >= 1 &&
nums[i] <= n &&
nums[nums[i] - 1] !== nums[i]
) {
const target = nums[i] - 1; // where nums[i] belongs
[nums[i], nums[target]] = [nums[target], nums[i]];
}
}
// Phase 2 — first index that doesn't hold i+1 is the answer.
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) return i + 1;
}
// Every slot 1..n is filled, so the answer is n+1.
return n + 1;
}n = nums.length. Every value we care about lives in [1, n], and the final answer is somewhere in [1, n + 1].nums[i] - 1. The while keeps placing whatever lands in nums[i]until it can't place anymore.nums[i] >= 1, nums[i] <= n (in range), and nums[nums[i] - 1] !== nums[i](its home doesn't already hold it). That last check skips duplicates and prevents an infinite loop.nums[i] to its home index target = nums[i] - 1. The destructuring swap exchanges the two slots in one line; we do not advance i, because a fresh value just arrived at nums[i].i should hold i + 1. The first index where it doesn't is the gap: return i + 1.1..n are all there, so the smallest missing positive is n + 1.n swaps total (each places a value in its final home), so it is O(n) amortized despite the inner while. Phase 2 is a single O(n) scan. Total O(n) time, O(1) extra space — we mutate nums in place.n slots, at most n distinct positives fit; if 1..n all appear, the gap is n + 1.nums[i]; the while keeps placing until nums[i] is settled before i advances.nums[nums[i] − 1] !== nums[i] — once a home already holds the value (a duplicate), we stop.nums[v − 1] as a present/absent bit, after first sanitizing non-positives — also O(n)/O(1).function firstMissingPositive(nums: number[]): number {
const n = nums.length;
// Phase 1 — place each value v in slot v-1 (cyclic sort).
for (let i = 0; i < n; i++) {
// Only swap when nums[i] is a useful, out-of-place value 1..n.
while (
nums[i] >= 1 &&
nums[i] <= n &&
nums[nums[i] - 1] !== nums[i]
) {
const target = nums[i] - 1; // where nums[i] belongs
[nums[i], nums[target]] = [nums[target], nums[i]];
}
}
// Phase 2 — first index that doesn't hold i+1 is the answer.
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) return i + 1;
}
// Every slot 1..n is filled, so the answer is n+1.
return n + 1;
}n swaps total (each places a value in its final home), so it is O(n) amortized despite the inner while. Phase 2 is a single O(n) scan. Total O(n) time, O(1) extra space — we mutate nums in place.The most obvious correct approach: sort the array, then walk it looking for the first positive integer that's skipped.
function firstMissingPositive(nums: number[]): number {
nums.sort((a, b) => a - b);
// The next positive integer we expect to see.
let expected = 1;
for (const v of nums) {
// Skip non-positives and duplicates of the current expected value.
if (v < expected) continue;
if (v === expected) {
expected++; // found it — advance to the next
} else {
// v > expected, so 'expected' was skipped: that's the gap.
return expected;
}
}
// Saw 1, 2, ..., expected-1 with no gap; answer is the next one.
return expected;
}O(n log n) sort misses the O(n) bar. Mutating the input via sort also destroys the original order.Dump every value into a set, then probe 1, 2, 3, … until one is missing. Hits O(n) time but spends O(n) space.
function firstMissingPositive(nums: number[]): number {
const seen = new Set<number>();
for (const v of nums) {
if (v > 0) seen.add(v); // only positives can ever be the answer
}
// The answer is in [1, n+1]; probe in order for the first miss.
let candidate = 1;
while (seen.has(candidate)) {
candidate++;
}
return candidate;
}O(n)-time solution and it leaves the input untouched, but the auxiliary set breaks the O(1)-space constraint — the whole point of the Hard variant.A swap-free sibling of cyclic sort: use the sign of nums[v − 1] as a present/absent bit after cleaning out-of-range values.
function firstMissingPositive(nums: number[]): number {
const n = nums.length;
// Step 1 — neutralize values that can't be the answer.
// Replace anything <= 0 or > n with n+1 (a harmless out-of-range value).
for (let i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) nums[i] = n + 1;
}
// Step 2 — for each in-range value v, mark slot v-1 negative as "present".
// Use the absolute value, since a slot may already be negated.
for (let i = 0; i < n; i++) {
const v = Math.abs(nums[i]);
if (v >= 1 && v <= n) {
const idx = v - 1;
if (nums[idx] > 0) nums[idx] = -nums[idx];
}
}
// Step 3 — first slot still positive means v=i+1 was never seen.
for (let i = 0; i < n; i++) {
if (nums[i] > 0) return i + 1;
}
// All of 1..n were marked present.
return n + 1;
}O(n)/O(1) bounds as cyclic sort and arguably easier to reason about (no nested while), but it requires the sanitizing pass first and only works because every relevant value lands in [1, n].| "smallest missing positive" | index-as-hash, answer in [1, n+1] |
| values are 1..n, O(1) space | cyclic sort (swap to slot v−1) |
| swap brings new value to nums[i] | while loop, do not advance i |
| home already holds value | duplicate guard, stop swapping |
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
const t = nums[i] - 1;
[nums[i], nums[t]] = [nums[t], nums[i]];
}
}
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) return i + 1;
}
return n + 1;n can hold at most n distinct positives; if 1..n all appear, the gap is n + 1.nums = [3,4,-1,1], the first missing positive is:i once sorted?[1,1]?nums = [1,2,3], the function returns: