Course4all

First Missing Positive

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

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

numstargetAction
[3,4,-1,1]1Sort -> [-1,1,3,4]
-11Skip (not positive)
11Match! target -> 2
323 > 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

SetCheckingFound?
{1, 2, 0}1Yes
{1, 2, 0}2Yes
{1, 2, 0}3No! 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]
1. nums[0]=3: Swap with nums[2] -> [-1, 4, 3, 1] 2. nums[1]=4: Swap with nums[3] -> [-1, 1, 3, 4] 3. nums[1]=1: Swap with nums[0] -> [1, -1, 3, 4] 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
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMerge K Sorted Arrays
Next Question →Insert Delete GetRandom O(1)