#77 · Arrays & Hashing

First Missing Positive

Given an unsorted integer array nums, return the smallest missing positive integer. The intended solution runs in O(n) time and uses O(1) auxiliary space.

HardLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Pigeonhole bound on the answer

With n numbers, at most n of the values 1 … n + 1 can be present, so the answer is always in 1 … n + 1. Anything ≤ 0 or > n is irrelevant and can be ignored.

Memory layout

No structure is needed for the argument; it only shrinks the search space to n + 1 candidates.

Operation	Cost
candidates to test	n + 1

Array as its own hash table (index = value − 1)

Value v in 1 … n has a natural home at index v − 1. If every value is moved to its home, the first index whose value is not index + 1 gives the missing positive. The array is the set, with no hashing at all.

Memory layout

The input array, rearranged in place; contiguous memory, cache friendly.

Operation	Cost
time	O(n): each swap places one value permanently
space	O(1)

Why it fits

The answer lies in a range of size n + 1, so the array positions themselves can act as presence flags for exactly the values that matter.
Each swap puts a value at its final home and a home is never swapped again, so total swaps ≤ n even though there is a nested while loop.
A hash set gives the same answer with O(n) extra memory; sorting gives it with O(n log n) time. The in-place version meets both bounds at once.

Why alternatives degrade

Min and max only:: Knowing the smallest and largest value says nothing about gaps in between.
Bitset of size n:: It needs O(n / 64) extra words; not O(1), though much smaller than a hash set.
Priority queue:: Draining a heap sorts the data: O(n log n).

Four approaches, from naive to production

1 · beginner

Test every candidate with a scan

time O(n²)space O(1)

For candidate = 1, 2, …, n + 1, scan the array to see if it is present. The first candidate that is not found is the answer.

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int candidate = 1; candidate <= n + 1; candidate++) {
        bool present = false;
        for (int x : nums) {
            if (x == candidate) { present = true; break; }
        }
        if (!present) return candidate;
    }
    return n + 1;
}

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int candidate = 1; candidate <= n + 1; candidate++) {
        boolean present = false;
        for (int x : nums) {
            if (x == candidate) { present = true; break; }
        }
        if (!present) return candidate;
    }
    return n + 1;
}

def first_missing_positive(nums):
    n = len(nums)
    for candidate in range(1, n + 2):
        present = False
        for x in nums:
            if x == candidate:
                present = True
                break
        if not present: return candidate
    return n + 1

function firstMissingPositive(nums: number[]): number {
  for (let candidate = 1; candidate <= nums.length + 1; candidate++) {
    let present = false;
    for (const x of nums) {
      if (x === candidate) { present = true; break; }
    }
    if (!present) return candidate;
  }
  return nums.length + 1;
}

Flaws & bottlenecks

Up to n + 1 candidates times n comparisons each.
Repeats the same linear scan for every candidate.
Too slow for n around 10⁵ and above.

Interviewer cross-questions

Why stop the candidates at n + 1?

Say: Pigeonhole: n numbers can cover at most n of the positives 1 … n + 1, so one of them is missing.

Do negative numbers or zero matter?

Say: No, they are never candidates, so they only waste scan time.

How do you avoid rescanning?

Say: Put all values in a set (O(1) lookup) or sort once.

2 · intermediate

Sort and walk

time O(n log n)space O(n)

Sort a copy, then walk through it with an expected counter that advances whenever the current value equals it. A bigger value means expected is missing.

int firstMissingPositive(vector<int>& nums) {
    vector<int> sorted(nums);
    sort(sorted.begin(), sorted.end());
    int expected = 1;
    for (int x : sorted) {
        if (x == expected) expected++;
        else if (x > expected) break;
    }
    return expected;
}

public int firstMissingPositive(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int expected = 1;
    for (int x : sorted) {
        if (x == expected) expected++;
        else if (x > expected) break;
    }
    return expected;
}

def first_missing_positive(nums):
    sorted_nums = sorted(nums)
    expected = 1
    for x in sorted_nums:
        if x == expected: expected += 1
        elif x > expected: break
    return expected

function firstMissingPositive(nums: number[]): number {
  const sorted = [...nums].sort((a, b) => a - b);
  let expected = 1;
  for (const x of sorted) {
    if (x === expected) expected++;
    else if (x > expected) break;
  }
  return expected;
}

Flaws & bottlenecks

Sorting is more than the problem needs.
The copy uses O(n) memory (sorting in place would modify the input).
Duplicates and non-positive values must be skipped correctly.

Interviewer cross-questions

Why does a duplicate not break the walk?

Say: A duplicate of an already counted value is smaller than expected, so neither branch fires and the loop simply continues.

Can you sort in place?

Say: Yes, if mutating the input is allowed; that removes the copy but not the O(n log n) time.

Is a faster approach possible?

Say: Yes: a hash set is O(n), and in-place placement is O(n) with O(1) space.

3 · advanced

Hash set and candidate walk

time O(n)space O(n)

Insert all numbers into a set, then test 1, 2, …, n in order; the first one missing is the answer, or n + 1 if all are present.

int firstMissingPositive(vector<int>& nums) {
    unordered_set<int> seen(nums.begin(), nums.end());
    int n = nums.size();
    for (int candidate = 1; candidate <= n; candidate++) {
        if (!seen.count(candidate)) return candidate;
    }
    return n + 1;
}

public int firstMissingPositive(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) seen.add(x);
    int n = nums.length;
    for (int candidate = 1; candidate <= n; candidate++) {
        if (!seen.contains(candidate)) return candidate;
    }
    return n + 1;
}

def first_missing_positive(nums):
    seen = set(nums)
    n = len(nums)
    for candidate in range(1, n + 1):
        if candidate not in seen: return candidate
    return n + 1

function firstMissingPositive(nums: number[]): number {
  const seen = new Set<number>(nums);
  for (let candidate = 1; candidate <= nums.length; candidate++) {
    if (!seen.has(candidate)) return candidate;
  }
  return nums.length + 1;
}

Flaws & bottlenecks

O(n) extra memory with hashing overhead (several times the array size in practice).
Hash collisions can degrade worst-case time in adversarial inputs.
Does not meet the O(1) space requirement.

Interviewer cross-questions

Why check only up to n?

Say: If all of 1 … n are present then the array holds exactly those values, and the answer is n + 1.

Could you use a boolean array instead of a set?

Say: Yes: a presence array of size n + 1 indexed by value (ignoring values outside 1 … n) is faster and smaller than a hash set.

How do you get to O(1) space?

Say: Reuse the input array as that presence table by placing each value at index value − 1.

4 · expert

In-place placement (cycle sort)

time O(n)space O(1)

Swap every value v in 1 … n to index v − 1. Then the first index i with nums[i] ≠ i + 1 gives the answer i + 1, or n + 1 when none exists.

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int j = nums[i] - 1;
            swap(nums[i], nums[j]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            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;
}

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1: return i + 1
    return n + 1

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

Flaws & bottlenecks

Modifies the input array; copy it first if the caller needs it unchanged.
The while loop must compare against the target value, not the target index, or duplicates cause an infinite loop.
Harder to reason about than the set version.

Interviewer cross-questions

Why is this O(n) despite the nested loop?

Say: Every swap puts one value at its permanent home. There are at most n homes, so at most n swaps in total.

Why nums[nums[i] - 1] !== nums[i] in the loop condition?

Say: If the home already holds the same value (a duplicate), swapping would do nothing and loop forever. The condition stops on duplicates.

What if the input must not be mutated?

Say: Copy it (O(n) space) or negate-marking tricks also mutate. Without mutation the O(1) space bound is impossible in this model.

Synchronized code walkthrough

Showing: Test every candidate with a scan — shares the player above; click any step to jump.

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int candidate = 1; candidate <= n + 1; candidate++) {
        bool present = false;
        for (int x : nums) {
            if (x == candidate) { present = true; break; }
        }
        if (!present) return candidate;
    }
    return n + 1;
}

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int candidate = 1; candidate <= n + 1; candidate++) {
        boolean present = false;
        for (int x : nums) {
            if (x == candidate) { present = true; break; }
        }
        if (!present) return candidate;
    }
    return n + 1;
}

def first_missing_positive(nums):
    n = len(nums)
    for candidate in range(1, n + 2):
        present = False
        for x in nums:
            if x == candidate:
                present = True
                break
        if not present: return candidate
    return n + 1

function firstMissingPositive(nums: number[]): number {
  for (let candidate = 1; candidate <= nums.length + 1; candidate++) {
    let present = false;
    for (const x of nums) {
      if (x === candidate) { present = true; break; }
    }
    if (!present) return candidate;
  }
  return nums.length + 1;
}

int firstMissingPositive(vector<int>& nums) {
    vector<int> sorted(nums);
    sort(sorted.begin(), sorted.end());
    int expected = 1;
    for (int x : sorted) {
        if (x == expected) expected++;
        else if (x > expected) break;
    }
    return expected;
}

public int firstMissingPositive(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int expected = 1;
    for (int x : sorted) {
        if (x == expected) expected++;
        else if (x > expected) break;
    }
    return expected;
}

def first_missing_positive(nums):
    sorted_nums = sorted(nums)
    expected = 1
    for x in sorted_nums:
        if x == expected: expected += 1
        elif x > expected: break
    return expected

function firstMissingPositive(nums: number[]): number {
  const sorted = [...nums].sort((a, b) => a - b);
  let expected = 1;
  for (const x of sorted) {
    if (x === expected) expected++;
    else if (x > expected) break;
  }
  return expected;
}

int firstMissingPositive(vector<int>& nums) {
    unordered_set<int> seen(nums.begin(), nums.end());
    int n = nums.size();
    for (int candidate = 1; candidate <= n; candidate++) {
        if (!seen.count(candidate)) return candidate;
    }
    return n + 1;
}

public int firstMissingPositive(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) seen.add(x);
    int n = nums.length;
    for (int candidate = 1; candidate <= n; candidate++) {
        if (!seen.contains(candidate)) return candidate;
    }
    return n + 1;
}

def first_missing_positive(nums):
    seen = set(nums)
    n = len(nums)
    for candidate in range(1, n + 1):
        if candidate not in seen: return candidate
    return n + 1

function firstMissingPositive(nums: number[]): number {
  const seen = new Set<number>(nums);
  for (let candidate = 1; candidate <= nums.length; candidate++) {
    if (!seen.has(candidate)) return candidate;
  }
  return nums.length + 1;
}

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int j = nums[i] - 1;
            swap(nums[i], nums[j]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            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;
}

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1: return i + 1
    return n + 1

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