First Missing Positive — Cyclic Sort Index Marking [LC 41]

Problem Statement#

Given an unsorted integer array nums, return the smallest missing positive integer. Must run in O(n) time and O(1) space.

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1

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

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

Why This Problem Matters#

LeetCode 41 is one of the most instructive hard problems in the array category — asked at Amazon, Google, and Microsoft. The O(n) time and O(1) space constraint rules out sorting (O(n log n)) and hash sets (O(n) space), forcing a deeper insight: use the array itself as a hash map.

The key mathematical observation — the answer must be in the range [1, n+1] — is the kind of constraint reasoning that FAANG interviewers test. Once you see that, the cyclic sort (place each valid number at its correct index) becomes natural. This exact "array as hash map" trick appears in Missing Number (LC 268), Find All Duplicates (LC 442), and Array Nesting (LC 565).

The Core Insight#

The answer is in [1, n+1]. With n elements, if all of 1 through n are present, the answer is n+1. Otherwise some number in [1, n] is missing.

Use the array as a hash map: For each valid number x where 1 <= x <= n, place it at index x-1. After rearrangement, scan from left to right — the first index i where nums[i] != i+1 is the answer. If all match, return n+1.

Cyclic sort: For each position, keep swapping nums[i] to its correct position nums[i]-1 until nums[i] is out of range or already correct.

Visual Dry Run#

nums = [3, 4, -1, 1], n = 4

Cyclic sort:

• i=0: nums[0]=3, correct pos=2. nums[2]=-1 ≠ 3, swap → [-1,4,3,1]. nums[0]=-1 out of range, skip.
• i=1: nums[1]=4, correct pos=3. nums[3]=1 ≠ 4, swap → [-1,1,3,4]. nums[1]=1, correct pos=0. nums[0]=-1 ≠ 1, swap → [1,-1,3,4]. nums[1]=-1, out of range, skip.
• i=2: nums[2]=3, correct pos=2. Already correct.
• i=3: nums[3]=4, correct pos=3. Already correct.

Final: [1, -1, 3, 4]

Scan: nums[0]=1=0+1 ✓. nums[1]=-1 ≠ 2 — first mismatch at i=1, answer = 2.

Solution (Optimal)#

class Solution:
    def firstMissingPositive(self, nums):
        n = len(nums)
        # Cyclic sort: place nums[i] at index nums[i]-1
        i = 0
        while i < n:
            j = nums[i] - 1
            if 1 <= nums[i] <= n and nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
            else:
                i += 1
        # Find first mismatch
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

var firstMissingPositive = function(nums) {
    const n = nums.length;
    let i = 0;
    while (i < n) {
        const j = nums[i] - 1;
        if (nums[i] >= 1 && nums[i] <= n && nums[i] !== nums[j]) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
        } else {
            i++;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }
    return n + 1;
};

Time: O(n) — each element placed at most once Space: O(1) — in-place rearrangement

Common Mistakes#

• Sorting — O(n log n), violates the time constraint
• Using a hash set — O(n) space, violates the space constraint
• Forgetting the nums[i] != nums[j] guard in cyclic sort — without it, equal elements cause an infinite swap loop
• Not checking 1 <= nums[i] <= n before computing j = nums[i] - 1 — negative numbers and values > n cause out-of-bounds
• Advancing i after every swap — should only advance when no valid swap is possible (else the swapped element at position i might also need placing)

Interview Tips#

• State the key bound: "the answer must be in [1, n+1] — this is the critical insight"
• Explain why: "with n numbers, if all 1..n are present the answer is n+1; otherwise some 1..n is missing"
• Walk through the cyclic sort loop — emphasize the guard nums[i] != nums[j] to prevent infinite loops on duplicates
• Mention that this modifies the input — ask if that's acceptable (it usually is)
• Alternative approach: mark indices by negation (negate nums[x-1] for each valid x, then find first positive) — same O(n) time, O(1) space

Follow-up Questions#

• Can you solve it without modifying the input? (Use index negation on a copy, or bitset — both O(n) space)
• What is the index-negation alternative? (For each valid x, negate nums[x-1]; first index i where nums[i] > 0 gives answer i+1)
• How does this extend to Find All Missing Numbers (LC 448)? (Same cyclic sort; collect all indices where nums[i] != i+1)
• What if the array contains duplicates? (The nums[i] != nums[j] guard handles this — duplicates end up at one position, others get skipped)
• What if the constraint were O(n log n) time? (Sort and scan — much simpler but slower)

Key Takeaways#

• LeetCode 41 is asked at Amazon, Google, and Microsoft — hard because O(n) time AND O(1) space are both required
• The answer must be in [1, n+1] — this bound is the key mathematical insight
• Cyclic sort places each valid number x at index x-1 using only swaps — O(1) space
• Guard against infinite loops: only swap when nums[i] != nums[j] (handles duplicates)
• After sorting, first index i where nums[i] != i+1 gives the answer; if all match, return n+1
• The "array as hash map" trick appears in LC 268, LC 442, LC 565 — learn it once, apply everywhere
• Alternative negation approach: negate nums[x-1] to mark x as seen, scan for first positive — same complexity, different implementation