Skip to content
In-Place Hashing Cracks LeetCode 41: O(n) Time, O(1) Space

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.

Rain's Path to Java Mastery
Rain's Path to Java Mastery
Rain's Path to Java Mastery

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: 1

This 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.

Flowchart of single-position placement logic
Flowchart of single-position placement logic

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]       → 1

Key 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."

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

algorithm interviewJava ImplementationFirst Missing PositiveCyclic SortIn-Place HashingLeetCode 41Pigeonhole PrincipleSign Marking
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.