First Missing Positive

Master this topic with zero to advance depth.

First Missing Positive

The missing positive must be in the range [1, n+1]. We can use the array itself to store presence information by placing each number x at index x-1. This is a constant space alternative to a HashSet.

Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space.

Visual Representation

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

Cyclic Sort (Move nums[i] to index nums[i]-1):
1. swap(3, -1) -> [-1, 4, 3, 1]
2. swap(4, 1)  -> [-1, 1, 3, 4]
3. swap(-1, 1) -> [1, -1, 3, 4]

Result:
Index 0: 1 (Correct)
Index 1: -1 (Incorrect! Should be 2)
Return: 2

Hard

Examples

Input: nums = [1,2,0]
Output: 3
The numbers in the range [1,2] are all in the array. 3 is the smallest missing positive.

Input: nums = [3,4,-1,1]
Output: 2
1 is in the array, but 2 is missing.

Approach 1

Level I: Brute Force (Sorting)

Intuition

Sort the input array. Since we are looking for the smallest missing positive integer (starting from 1), iterate through the sorted array and keep track of a target (starting at 1). If the current number equals target, increment target. If we find a number greater than target or reach the end, target is the answer.

⏱ O(N log N) due to sorting.💾 O(1) if sorting is in-place, otherwise O(N).

Detailed Dry Run

nums	target	Action
[3,4,-1,1]	1	Sort -> [-1,1,3,4]
-1	1	Skip (not positive)
1	1	Match! target -> 2
3	2	3 > 2, Stop.
Result: 2	-	-

java

import java.util.Arrays;

public class Main {
    public static int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int target = 1;
        for (int num : nums) {
            if (num == target) target++;
            else if (num > target) break;
        }
        return target;
    }
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(firstMissingPositive(nums)); // Output: 2
    }
}

Approach 2

Level II: Better Solution (HashSet)

Intuition

Store all numbers in a HashSet for O(1) lookups. Iterate from 1 up to N+1 (where N is array size). The first number not present in the set is the smallest missing positive integer.

⏱ O(N) to populate the set and iterate up to N+1.💾 O(N) to store elements in the set.

Detailed Dry Run

Set	Checking	Found?
{1, 2, 0}	1	Yes
{1, 2, 0}	2	Yes
{1, 2, 0}	3	No! Result=3

java

import java.util.*;

public class Main {
    public static int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        for (int i = 1; i <= nums.length + 1; i++) {
            if (!set.contains(i)) return i;
        }
        return 1;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 0};
        System.out.println(firstMissingPositive(nums)); // Output: 3
    }
}

Approach 3

Level III: Optimal Solution (Cyclic Sort)

Intuition

Use the array itself as a 'hash map'. Since the answer must be in the range [1, N+1], try to place every number x in the range [1, N] at index x-1. For example, 1 should be at index 0, 2 at index 1, etc. After one pass of swapping, the first index i where nums[i] != i+1 gives the missing number.

⏱ O(N) - even with the `while` loop, each element is moved to its correct position at most once.💾 O(1) extra space as we reorder the input array.

Detailed Dry Run

Cyclic Sort Visualization

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

nums[0]=3: Swap with nums[2] -> [-1, 4, 3, 1]
nums[1]=4: Swap with nums[3] -> [-1, 1, 3, 4]
nums[1]=1: Swap with nums[0] -> [1, -1, 3, 4]
Done! nums[1] is -1, which is not 1+1=2. Answer: 2

java

public class Main {
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(firstMissingPositive(nums)); // Output: 2
    }
}

← Previous QuestionMerge K Sorted Arrays

Next Question →Insert Delete GetRandom O(1)

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.