First Missing Positive

HARD✓ CHIP-TIMEDLC #41 — FULL STATEMENT ↗

The drill: The smallest positive integer an unsorted array is missing — with the real fight in the bounds: linear time, constant extra space. Length n pins the answer inside 1..n+1, which is exactly what lets the array double as its own hash table.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An unsorted list of integers sits in front of you, some negative, some zero, some repeated, and the job is to name the smallest positive whole number nowhere among them.

Nothing about the order matters and nothing needs to be produced beyond that single integer. Negative values and zero never count as candidates — the hunt only cares about 1, 2, 3, and onward.

Because the array holds n entries, the missing number can never be larger than n+1, no matter how the values are scattered. That ceiling is what keeps the drill solvable inside a strict linear-time, constant-space budget.

EX 01

nums = [1]

→ 2

MINIMUM SIZE — THE RUN OF ONE IS COMPLETE

EX 02

nums = [-4]

→ 1

SINGLE NEGATIVE, 1 NEVER SHOWED UP

EX 03

nums = [2, 3, 7, 1]

→ 4

CHAIN 1..3 HOLDS, THEN SNAPS

array length ranges from a single element up to a few hundred thousand
values can be negative, zero, duplicated, or wildly out of range
the missing number is always between 1 and length+1, inclusive
solutions on this course must run in linear time using constant extra space

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Sorting answers it, and a hash set answers it faster — but one busts the time bound and the other the space bound. First shrink the battlefield: with only n values, how large can the answer possibly be?

HINT 2 THE STRUCTURE

The answer lives in 1..n+1 — the array's own index range, shifted by one. So slot i can act as the bucket for value i+1: the array can become its own hash table.

HINT 3 ONE STEP FROM THE ANSWER

While a slot holds a value in 1..n whose home slot holds something different, swap it home — each swap parks one value for good, so the work stays linear. Then the first slot whose tenant isn't i+1 names the answer; if every tenant is right, it's n+1.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ARRAY BECOMES THE MAPPATTERN · CYCLIC SORTnums = [2, 3, 7, 1]

STEP 1

Length 4 pins the answer inside 1..5. Slot 0 holds 2, whose home is slot 1 — send it there.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/first-missing-positive.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            # keep sending this slot's value home until the slot settles
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                home = nums[i] - 1
                nums[i], nums[home] = nums[home], nums[i]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 12 LN

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        candidate = 1
        while candidate in nums:  # a full membership scan per candidate
            candidate += 1
        return candidate  # at most n + 1: n values cannot cover all of 1..n+1

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 6 LN

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // keep sending this slot's value home until the slot settles
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int home = nums[i] - 1;
                int tmp = nums[home];
                nums[home] = nums[i];
                nums[i] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 20 LN

class Solution {
    public int firstMissingPositive(int[] nums) {
        int candidate = 1; // at most n + 1: n values cannot cover all of 1..n+1
        while (contains(nums, candidate)) {
            candidate++;
        }
        return candidate;
    }

    private boolean contains(int[] nums, int target) {
        for (int v : nums) {
            if (v == target) {
                return true;
            }
        }
        return false;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 18 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED