Skip to main content
CodePeetCodePeet
CodePeet 250

First Missing Positive

HARDProblemSolveExternal Links

Description

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

The challenge lies in the strict efficiency requirement: your solution must run in O(n) time and use only O(1) extra space (beyond the input array itself). This means common approaches like sorting or using a hash set are either too slow or use too much memory.

Positive integers start from 1, 2, 3, ... and you need to find the first one that is missing from the given array. The array may contain negative numbers, zeros, duplicates, and very large values — all of which are distractions from the actual answer.

Examples

Example 1

Input: nums = [1, 2, 0]

Output: 3

Explanation: The positive integers 1 and 2 are both present in the array. The next positive integer is 3, and it is missing. Zero is not a positive integer, so it does not affect the answer.

Example 2

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

Output: 2

Explanation: The positive integer 1 is present, but 2 is not. Even though 3 and 4 are present, the smallest missing positive is 2. Negative numbers like -1 are ignored when searching for positive integers.

Example 3

Input: nums = [7, 8, 9, 11, 12]

Output: 1

Explanation: None of the values 1 through 6 are present. Since 1 is the smallest positive integer and it is missing, the answer is 1. The presence of large numbers (7, 8, 9, 11, 12) is irrelevant because none of the basic positive integers starting from 1 are in the array.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to find the first missing positive is to simply check each positive integer one by one: is 1 in the array? Is 2 in the array? Is 3 in the array? And so on, until we find one that is absent.

Think of it like a teacher calling roll for students numbered 1, 2, 3, ... The teacher calls each number in order and checks if that student is present. The first number where no one answers is the missing student.

For each candidate number, we scan the entire array looking for it. If we find it, we move on to the next candidate. If we do not find it after checking every element, that candidate is our answer.

A key observation is that the answer is always between 1 and n+1 (where n is the array length). Why? If the array contains all values from 1 to n, the answer is n+1. Otherwise, at least one value in [1, n] is missing.

Step-by-Step Explanation

Let's trace through with nums = [3, 4, -1, 1]:

Step 1: Check if 1 is in the array.

  • Scan: 3≠1, 4≠1, -1≠1, 1==1. Found!
  • 1 is present, move to next candidate.

Step 2: Check if 2 is in the array.

  • Scan: 3≠2, 4≠2, -1≠2, 1≠2. Not found!
  • 2 is missing from the array.

Step 3: Return 2 as the first missing positive.

We only needed to check candidates 1 and 2. In the worst case (e.g., nums = [1, 2, 3, ..., n]), we would check all n candidates, each requiring an O(n) scan, resulting in O(n²) total work.

Brute Force — Checking Each Positive Integer — Watch how we test each positive integer starting from 1 by scanning the entire array for it. The first candidate not found is our answer.

Algorithm

  1. For each candidate from 1 to n+1:
    a. Scan the entire array looking for this candidate
    b. If the candidate is not found, return it
  2. If all candidates 1 to n are found, return n+1

Code

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int candidate = 1; candidate <= n + 1; candidate++) {
            bool found = false;
            for (int j = 0; j < n; j++) {
                if (nums[j] == candidate) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return candidate;
            }
        }
        return n + 1;
    }
};
class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)
        for candidate in range(1, n + 2):
            found = False
            for num in nums:
                if num == candidate:
                    found = True
                    break
            if not found:
                return candidate
        return n + 1
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int candidate = 1; candidate <= n + 1; candidate++) {
            boolean found = false;
            for (int j = 0; j < n; j++) {
                if (nums[j] == candidate) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return candidate;
            }
        }
        return n + 1;
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case, the array contains [1, 2, 3, ..., n], and we check each of the n candidates. For each candidate, we scan up to n elements. That gives n × n = n² comparisons. Even when the answer is found early, the worst case is still quadratic.

Space Complexity: O(1)

We only use a few variables (candidate, found, loop counter). No additional data structures are allocated, so space usage is constant regardless of input size.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity. With n up to 10^5, this means up to 10^10 operations — far too slow for typical time limits of 1-2 seconds.

The core inefficiency is that for every candidate number, we perform a full linear scan of the array. We are repeatedly traversing the same data without remembering anything from previous scans.

The key insight: if we could answer "is number X present?" in O(1) time instead of O(n), we would reduce the total time from O(n²) to O(n). A hash set provides exactly this capability — store all values, then check each candidate in constant time.

Better Approach - Hash Set

Intuition

Instead of scanning the array repeatedly for each candidate, we can store all array values into a hash set first. Then, we simply check each positive integer starting from 1: is it in the set? The first one that is not in the set is our answer.

Imagine you have a jar of numbered balls. Instead of digging through the jar every time you want to check a specific number, you first lay all the balls on a table organized by number (the hash set). Now checking if a specific number exists is instantaneous — you just look at the spot where it should be.

This reduces the time to O(n) but uses O(n) extra space for the set. The problem explicitly asks for O(1) auxiliary space, so this approach satisfies the time requirement but violates the space requirement.

Step-by-Step Explanation

Let's trace through with nums = [3, 4, -1, 1]:

Step 1: Build the hash set from all array elements.

  • Insert 3 → set = {3}
  • Insert 4 → set = {3, 4}
  • Insert -1 → set = {3, 4, -1}
  • Insert 1 → set = {3, 4, -1, 1}

Step 2: Check candidate 1.

  • Is 1 in the set? Yes. Move on.

Step 3: Check candidate 2.

  • Is 2 in the set? No!

Step 4: Return 2 as the first missing positive.

Each lookup in the hash set is O(1) on average, so checking all candidates takes O(n) total.

Hash Set — Build and Query for Missing Positive — First we store all array values in a hash set, then we check each positive integer starting from 1 to find the first one that is absent.

Algorithm

  1. Insert all elements of nums into a hash set
  2. For candidate from 1 to n+1:
    • If candidate is NOT in the set, return it
  3. Return n+1 (if all values 1..n are present)

Code

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int n = nums.size();
        for (int candidate = 1; candidate <= n + 1; candidate++) {
            if (numSet.find(candidate) == numSet.end()) {
                return candidate;
            }
        }
        return n + 1;
    }
};
class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        num_set = set(nums)
        n = len(nums)
        for candidate in range(1, n + 2):
            if candidate not in num_set:
                return candidate
        return n + 1
class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        int n = nums.length;
        for (int candidate = 1; candidate <= n + 1; candidate++) {
            if (!numSet.contains(candidate)) {
                return candidate;
            }
        }
        return n + 1;
    }
}

Complexity Analysis

Time Complexity: O(n)

Building the hash set takes O(n) time (one insertion per element, each O(1) on average). Checking candidates 1 through at most n+1 takes O(n) time (one O(1) lookup per candidate). Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

The hash set stores up to n elements, requiring O(n) additional space. This violates the O(1) space constraint of the problem, making this approach correct but not optimal for this problem's requirements.

Why This Approach Is Not Efficient

While the hash set approach achieves O(n) time, it uses O(n) extra space. The problem explicitly requires O(1) auxiliary space.

The question becomes: can we achieve the same O(1) lookup behavior without using extra memory? The answer lies in a powerful insight — we can repurpose the input array itself as our "hash set".

Since the answer is always in the range [1, n+1], we only care about values between 1 and n. An array of size n has indices 0 through n-1. If we could place each value v at index v-1 (i.e., value 1 at index 0, value 2 at index 1, etc.), then the first index i where nums[i] ≠ i+1 gives us the missing positive i+1. This is the cyclic sort technique.

Optimal Approach - Cyclic Sort (Index as Hash)

Intuition

The brilliant idea behind this approach is to use the array itself as a hash map. Since we are looking for the first missing positive in the range [1, n], we can try to place each number at its "correct" position: value 1 should be at index 0, value 2 at index 1, value 3 at index 2, and so on.

Imagine you have a row of n mailboxes labeled 1 through n. You receive a bag of letters, each addressed to a mailbox number. Some letters have invalid addresses (negative numbers or numbers greater than n). You go through the bag and for each valid letter, you place it in the correct mailbox. If a mailbox already has the right letter, you skip it. After processing all letters, you walk along the mailboxes from left to right — the first empty mailbox number is your answer.

The algorithm works in two phases:

  1. Placement phase: For each element, if it is in the range [1, n] and not already in its correct position, swap it to where it belongs. Keep swapping until the current position holds either an out-of-range value or a value already at its correct spot.
  2. Detection phase: Scan the array from left to right. The first index i where nums[i] ≠ i + 1 means the value i + 1 is missing. If all positions are correct, the answer is n + 1.

Step-by-Step Explanation

Let's trace through with nums = [3, 4, -1, 1]:

Phase 1: Placement (Cyclic Sort)

Step 1: i=0, nums[0]=3. Value 3 should be at index 2. Is nums[0] (3) ≠ nums[2] (-1)? Yes, swap.

  • After swap: nums = [-1, 4, 3, 1]

Step 2: i=0, nums[0]=-1. Value -1 is out of range [1,4]. Skip, move to i=1.

Step 3: i=1, nums[1]=4. Value 4 should be at index 3. Is nums[1] (4) ≠ nums[3] (1)? Yes, swap.

  • After swap: nums = [-1, 1, 3, 4]

Step 4: i=1, nums[1]=1. Value 1 should be at index 0. Is nums[1] (1) ≠ nums[0] (-1)? Yes, swap.

  • After swap: nums = [1, -1, 3, 4]

Step 5: i=1, nums[1]=-1. Value -1 is out of range. Skip, move to i=2.

Step 6: i=2, nums[2]=3. Value 3 should be at index 2. nums[2]=3 is already at the correct position. Skip, move to i=3.

Step 7: i=3, nums[3]=4. Value 4 should be at index 3. Already correct. Skip.

Phase 2: Detection

Step 8: Check index 0: nums[0]=1 == 0+1=1. Correct.

Step 9: Check index 1: nums[1]=-1 ≠ 1+1=2. Mismatch found!

Step 10: Return 2 as the first missing positive.

Cyclic Sort — Place Each Value at Its Correct Index — Watch how each value is swapped to its 'home' index (value v goes to index v-1). After placement, the first mismatch reveals the missing positive.

Algorithm

Phase 1 — Placement (Cyclic Sort):

  1. For each index i from 0 to n-1:
    • While nums[i] is in range [1, n] AND nums[i] is not at its correct position (i.e., nums[i] ≠ nums[nums[i]-1]):
      • Swap nums[i] with nums[nums[i]-1]

Phase 2 — Detection:
2. For each index i from 0 to n-1:

  • If nums[i] ≠ i+1, return i+1
  1. If all positions are correct, return n+1

Code

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        // Phase 1: Place each value at its correct index
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n 
                   && nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        
        // Phase 2: Find first position where value != index+1
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};
class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)
        
        # Phase 1: Place each value at its correct index
        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                target = nums[i] - 1
                nums[i], nums[target] = nums[target], nums[i]
        
        # Phase 2: Find first position where value != index+1
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        
        return n + 1
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // Phase 1: Place each value at its correct index
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n 
                   && nums[i] != nums[nums[i] - 1]) {
                int target = nums[i] - 1;
                int temp = nums[i];
                nums[i] = nums[target];
                nums[target] = temp;
            }
        }
        
        // Phase 2: Find first position where value != index+1
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
}

Complexity Analysis

Time Complexity: O(n)

Although there is a while loop nested inside the for loop, the total number of swaps across the entire execution is at most n. Each swap places at least one element at its correct position, and once an element is correctly placed, it is never moved again. So the inner while loop runs at most n times in total across all iterations of the outer for loop. The detection phase is a single pass of O(n). Total: O(n) + O(n) = O(n).

Space Complexity: O(1)

We modify the input array in-place. No additional data structures are used beyond a few temporary variables for swapping. This satisfies the O(1) auxiliary space requirement.