First Missing Positive (LC 41)

Pattern: Index mapping / Cyclic sort (in-place reordering)
Difficulty: Hard
Key Concept: The answer lies in [1, n] for array length n; place each valid number x at index x - 1, then scan for the first mismatch.

Problem Statement

Given an unsorted integer array nums, return the smallest positive integer that does not appear in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space (excluding the input array; modifying nums in place is allowed on LeetCode for this problem).

Input: Integer array nums.
Output: Smallest integer k >= 1 such that k is not in nums.

---

1. Algorithm & Pseudocode

Brute force (sort then scan)

1. Sort nums (e.g. ascending).
2. Scan from the smallest positive upward: track expected = 1; for each positive value in sorted order, if it equals expected, increment expected; skip duplicates and non-positives.
3. Alternatively: after sort, find first gap in the sequence of positives.
4. Return expected or the first missing in the linear scan logic.

Optimal (index placement / cyclic sort)

1. Let n = nums.length. Ignore any number outside [1, n] — it cannot be the answer (the answer is at most n + 1, and we only have n slots to mark 1..n).
2. For i from 0 to n - 1:
   • While nums[i] is in [1, n] and nums[i] is not already at its correct index (nums[i] != nums[nums[i] - 1]):
     • Swap nums[i] with nums[nums[i] - 1] (put nums[i] at index nums[i] - 1).
3. Scan i from 0 to n - 1: if nums[i] != i + 1, return i + 1.
4. If every position matches, return n + 1.

Swap condition nums[i] != nums[nums[i] - 1]: Avoids infinite swap when duplicates exist at the target index.

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why answer ∈ [1, n + 1]? There are only n numbers in the array. In the best case they could be exactly 1..n, so the missing positive is n + 1. Otherwise some k in 1..n is missing — that is the smallest missing positive (we find the smallest by scanning from 1 upward via index order).
• Why ignore ≤ 0 and > n? They do not help mark which of 1..n are present; they belong in “junk” positions until displaced by valid numbers.
• Why swap instead of a hash set? A set uses O(n) extra space; swaps reorder in place in O(n) time (each swap places at least one number correctly; amortized linear work).
• Java swap: You need a temporary variable — no tuple unpacking like Python’s a, b = b, a.
• Bounds: nums[nums[i] - 1] is safe only when nums[i] is in [1, n]; the while condition enforces that before indexing.

---

3. The Dry Run

nums = [3, 4, -1, 1], n = 4. Goal: each value v in 1..4 should end at index v - 1.

Main loop trace (outer index i; inner while may perform multiple swaps)

step	i	nums	action
init	—	[3, 4, -1, 1]	—
1	0	[-1, 4, 3, 1]	swap index 0 ↔ 2 (3 ↔ -1)
2	0	(while ends: -1 not in [1,4])	—
3	1	[1, -1, 3, 4]	swap index 1 ↔ 3 (4 ↔ 1), then swap 1 ↔ 0 (1 ↔ -1)
4	2	[1, -1, 3, 4]	3 already at index 2
5	3	[1, -1, 3, 4]	4 already at index 3

Final scan

i	nums[i]	i + 1	match?
0	1	1	yes
1	-1	2	no → return 2

---

4. Java Solution

Brute Force

import java.util.Arrays;

public int firstMissingPositive(int[] nums) {
    Arrays.sort(nums);
    int expected = 1;
    for (int x : nums) {
        if (x <= 0) {
            continue;
        }
        if (x == expected) {
            expected++;
        } else if (x > expected) {
            break;
        }
        // x < expected: duplicate of a value we already counted; skip
    }
    return expected;
}

Time: O(n log n) for sorting.
Space: O(1) extra if sort is in-place (Java Arrays.sort on int[] is in-place).

Optimal

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
            int j = nums[i] - 1;
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

Time: O(n) — each swap places at least one element in its final position; each index’s while-loop runs limited times overall.
Space: O(1) extra.

---

5. The “Java vs. Others” Edge

• Swap with temp: Java has no built-in destructuring assignment; use a third variable (or XOR swap tricks, which are rarely clearer).
• Array bounds: If nums[i] were outside [1, n], nums[nums[i] - 1] could throw ArrayIndexOutOfBoundsException. The while guard requires nums[i] in range before using it as an index — keep that order.
• C++ contrast: Out-of-bounds access in C++ raw arrays is undefined behavior; Java fails fast with an exception if you slip up.
• Filtering [1, n]: Numbers outside this range are noise for “which of 1..n is missing”; the algorithm only moves values that can sit at a meaningful index.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n log n)	O(1) extra	Sort then single scan for smallest missing positive.
Optimal	O(n)	O(1)	In-place swaps to index map; final linear verification.