The Hard Problem

LC 41: First Missing Positive. Rated Hard. Here's the problem statement:

1
Input:  [3, 4, -1, 1]
2
Output: 2
3
4
Input:  [1, 2, 0]
5
Output: 3

Given an unsorted integer array, find the smallest missing positive integer. Must run in O(n) time and O(1) extra space. That constraint — constant space — is what makes it Hard. You can't use a hash set. You can't sort with mergesort. You need to rearrange the array in place.

But look at the first input: [3, 4, -1, 1]. The values 1, 3, and 4 are positive integers with valid “home addresses” in an array of length 4. Value 1 belongs at index 0, value 3 belongs at index 2, value 4 belongs at index 3. They're legitimate mail. The -1? That's junk mail — a negative number has no home in our [1, n] mailroom. It should be ignored, not sorted.

The problem also mentions 0 (not positive, so junk) and values larger than n (oversized packages — no mailbox exists for them). But once you filter out the junk, what remains? Legitimate letters that know their home addresses. You already know how to sort those. You already know how to scan for mismatches. You already know every move. The only new idea is: skip the junk.

First Missing Positive

Negatives. Gaps. This looks nothing like cyclic sort... or does it?
3
0
4
1
-1
2
1
3

Which values CAN be placed using cyclic sort? Range is 14.

Same Pattern, Wider Guard

Here's the complete solution. Read it slowly — you've seen every piece before:

1
function firstMissingPositive(nums: number[]): number {
2
  const n = nums.length;
3
4
  // Step 1: Cyclic sort — place each value at its home
5
  for (let i = 0; i < n; i++) {
6
    while (
7
      nums[i] > 0 &&            // not junk (negative/zero)
8
      nums[i] <= n &&            // not oversized (> n)
9
      nums[i] !== nums[nums[i] - 1]  // not already home / duplicate
10
    ) {
11
      const home = nums[i] - 1;
12
      [nums[i], nums[home]] = [nums[home], nums[i]];
13
    }
14
  }
15
16
  // Step 2: Scan for first mismatch
17
  for (let i = 0; i < n; i++) {
18
    if (nums[i] !== i + 1) return i + 1;
19
  }
20
21
  // All positions filled — answer is n + 1
22
  return n + 1;
23
}

Three moves: filter, place, scan. The while condition has two extra guards — nums[i] > 0 and nums[i] <= n — that skip junk mail and oversized packages. The duplicate guard (nums[i] !== nums[nums[i] - 1]) is the same one you learned in the previous lesson. The address formula (nums[i] - 1) is the same one you discovered when you first placed values by hand. The scan is the same mismatch scan, but this time you only care about the first missing value, so you return immediately.

If every position 0 through n-1 holds its correct value, then the array is a perfect permutation of [1, n] and the answer is n + 1 — the next positive integer after the range.

You just solved a Hard problem with an idea you discovered by sorting five numbers. The address formula, the settle loop, the duplicate guard, the mismatch scan — every piece was built one lesson at a time. That's the power of cyclic sort: one core insight, layered incrementally, solving problems from Easy to Hard.