Facebook Pixel

41. First Missing Positive

HardArrayHash Table
Leetcode Link

Problem Description

You are given an unsorted integer array nums. Your task is to find the smallest positive integer that is not present in the array.

The key requirements are:

  • Find the smallest missing positive integer (starting from 1, 2, 3, ...)
  • Your algorithm must run in O(n) time complexity
  • You can only use O(1) auxiliary space (constant extra space)

For example:

  • If nums = [1, 2, 0], the answer is 3 because 1 and 2 are present, but 3 is missing
  • If nums = [3, 4, -1, 1], the answer is 2 because 1 is present, but 2 is missing
  • If nums = [7, 8, 9, 11, 12], the answer is 1 because no positive integers starting from 1 are present

The solution uses an in-place swapping technique. Since the answer must be in the range [1, n+1] where n is the length of the array, we can rearrange the array so that each positive integer x within range [1, n] is placed at index x-1. After this rearrangement, we scan through the array to find the first position where the value doesn't match its expected position plus one. This gives us the smallest missing positive integer.

The algorithm works in two phases:

  1. Rearrangement phase: For each number in the valid range [1, n], swap it to its correct position repeatedly until the current position holds either an out-of-range number or the correct number
  2. Scanning phase: Check each position to find where nums[i] != i+1, which indicates the first missing positive integer
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight comes from recognizing that the smallest missing positive integer must be bounded. If we have an array of length n, the smallest missing positive can only be in the range [1, n+1]. Why? Because even if the array contains all the smallest positive integers perfectly (like [1, 2, 3, ..., n]), the answer would be n+1. In any other case, there's a gap somewhere in [1, n], and that gap is our answer.

This bounded range gives us a powerful idea: we can use the array indices themselves as a hash table! Since array indices go from 0 to n-1, we can map positive integers 1 to n to indices 0 to n-1 respectively. Each positive integer x should ideally be at position x-1.

But how can we use the array as its own hash table without using extra space? The trick is to rearrange the elements in-place. We can swap each valid number to its "home" position. For example, if we encounter the number 3, it should go to index 2 (position 3-1).

The beauty of this approach is that after rearrangement:

  • Numbers outside the range [1, n] stay wherever they end up (we don't care about them)
  • Numbers within [1, n] are placed at their corresponding positions if possible
  • The first position where nums[i] != i+1 tells us that i+1 is missing

This works because we're essentially creating a presence indicator using the array itself. If position i contains i+1, then i+1 is present in the original array. If not, then i+1 is missing. The first such missing number is our answer.

The swapping process ensures that each element gets moved at most once to its final position, maintaining O(n) time complexity, while using the input array itself as storage maintains O(1) space complexity.

Solution Approach

The implementation follows the in-place swap strategy to rearrange the array such that each number x in range [1, n] is placed at position x-1.

Phase 1: In-place Rearrangement

We iterate through each position i in the array. For the current nums[i], we check if:

  1. It's within the valid range: 1 <= nums[i] <= n
  2. It's not already at its correct position: nums[i] != nums[nums[i] - 1]

If both conditions are met, we swap nums[i] with the element at its target position nums[i] - 1. The key detail is using a while loop instead of if because after swapping, the new element at position i might also need to be moved to its correct position.

for i in range(n):
    while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
        j = nums[i] - 1
        nums[i], nums[j] = nums[j], nums[i]

The condition nums[i] != nums[nums[i] - 1] is crucial - it prevents infinite loops when a duplicate exists. If nums[i] equals the value at its target position, we know there's a duplicate and we should stop swapping.

Phase 2: Finding the First Missing Positive

After rearrangement, we scan the array linearly. At each position i, we check if nums[i] == i + 1. The first position where this condition fails indicates that i + 1 is the smallest missing positive integer.

for i in range(n):
    if nums[i] != i + 1:
        return i + 1

If all positions satisfy nums[i] == i + 1, it means the array contains all integers from 1 to n, so the smallest missing positive is n + 1.

return n + 1

Time and Space Complexity:

  • Time: O(n) - Although we have nested loops, each element is moved at most once to its final position
  • Space: O(1) - We only use a constant amount of extra variables for swapping

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the algorithm with nums = [3, 4, -1, 1]:

Initial State:

  • Array: [3, 4, -1, 1]
  • Length n = 4, so valid range is [1, 4]

Phase 1: In-place Rearrangement

Position i = 0:

  • Current value: nums[0] = 3
  • Is 3 in range [1, 4]? Yes
  • Target position for 3: index 2 (3-1)
  • Is nums[0] != nums[2]? Compare 3 != -1? Yes
  • Swap: [3, 4, -1, 1] → [-1, 4, 3, 1]
  • Check new nums[0] = -1: Not in range [1, 4], stop while loop

Position i = 1:

  • Current value: nums[1] = 4
  • Is 4 in range [1, 4]? Yes
  • Target position for 4: index 3 (4-1)
  • Is nums[1] != nums[3]? Compare 4 != 1? Yes
  • Swap: [-1, 4, 3, 1] → [-1, 1, 3, 4]
  • Check new nums[1] = 1: In range [1, 4]
  • Target position for 1: index 0 (1-1)
  • Is nums[1] != nums[0]? Compare 1 != -1? Yes
  • Swap: [-1, 1, 3, 4] → [1, -1, 3, 4]
  • Check new nums[1] = -1: Not in range [1, 4], stop while loop

Position i = 2:

  • Current value: nums[2] = 3
  • Is 3 in range [1, 4]? Yes
  • Target position for 3: index 2 (3-1)
  • Is nums[2] != nums[2]? Compare 3 != 3? No
  • Already at correct position, no swap needed

Position i = 3:

  • Current value: nums[3] = 4
  • Is 4 in range [1, 4]? Yes
  • Target position for 4: index 3 (4-1)
  • Is nums[3] != nums[3]? Compare 4 != 4? No
  • Already at correct position, no swap needed

After Rearrangement: [1, -1, 3, 4]

Phase 2: Finding the First Missing Positive

Check each position:

  • Position 0: nums[0] = 1, should be 1 ✓
  • Position 1: nums[1] = -1, should be 2 ✗

The first mismatch is at position 1, where we expected 2 but found -1.

Answer: 2

The smallest missing positive integer is 2.

Solution Implementation

1class Solution:
2    def firstMissingPositive(self, nums: List[int]) -> int:
3        """
4        Find the first missing positive integer in an unsorted array.
5        Uses cyclic sort to place each positive integer at its correct position.
6        Time: O(n), Space: O(1)
7        """
8        n = len(nums)
9      
10        # Phase 1: Place each positive integer at its correct position
11        # For a positive integer k (where 1 <= k <= n), place it at index k-1
12        for i in range(n):
13            # Keep swapping current element to its correct position
14            # until current position has correct element or invalid element
15            while (1 <= nums[i] <= n and 
16                   nums[i] != nums[nums[i] - 1]):
17                # Calculate target index for current element
18                target_index = nums[i] - 1
19                # Swap current element with element at target position
20                nums[i], nums[target_index] = nums[target_index], nums[i]
21      
22        # Phase 2: Find the first position where element doesn't match expected value
23        # Position i should contain value i+1
24        for i in range(n):
25            if nums[i] != i + 1:
26                return i + 1
27      
28        # All positions [0, n-1] contain correct values [1, n]
29        # So the first missing positive is n+1
30        return n + 1
31
1class Solution {
2    /**
3     * Finds the smallest missing positive integer in an unsorted array.
4     * Uses cyclic sort to place each positive number at its corresponding index.
5     * Time Complexity: O(n), Space Complexity: O(1)
6     * 
7     * @param nums the input array
8     * @return the smallest missing positive integer
9     */
10    public int firstMissingPositive(int[] nums) {
11        int arrayLength = nums.length;
12      
13        // Phase 1: Place each positive number at its correct position
14        // For a number k where 1 <= k <= n, place it at index k-1
15        for (int currentIndex = 0; currentIndex < arrayLength; currentIndex++) {
16            // Keep swapping while:
17            // 1. Current number is positive
18            // 2. Current number is within valid range [1, n]
19            // 3. Current number is not already at its correct position
20            while (nums[currentIndex] > 0 && 
21                   nums[currentIndex] <= arrayLength && 
22                   nums[currentIndex] != nums[nums[currentIndex] - 1]) {
23                // Swap current number to its correct position
24                int targetIndex = nums[currentIndex] - 1;
25                swap(nums, currentIndex, targetIndex);
26            }
27        }
28      
29        // Phase 2: Find the first position where number doesn't match index + 1
30        for (int index = 0; index < arrayLength; index++) {
31            if (nums[index] != index + 1) {
32                // The missing positive is index + 1
33                return index + 1;
34            }
35        }
36      
37        // All numbers from 1 to n are present, so the answer is n + 1
38        return arrayLength + 1;
39    }
40  
41    /**
42     * Helper method to swap two elements in the array
43     * 
44     * @param nums the array
45     * @param firstIndex index of the first element
46     * @param secondIndex index of the second element
47     */
48    private void swap(int[] nums, int firstIndex, int secondIndex) {
49        int temp = nums[firstIndex];
50        nums[firstIndex] = nums[secondIndex];
51        nums[secondIndex] = temp;
52    }
53}
54
1class Solution {
2public:
3    int firstMissingPositive(vector<int>& nums) {
4        int n = nums.size();
5      
6        // Place each positive integer at its correct position
7        // nums[i] should be at index nums[i] - 1
8        // For example: 1 should be at index 0, 2 should be at index 1, etc.
9        for (int i = 0; i < n; ++i) {
10            // Keep swapping while:
11            // 1. Current number is positive
12            // 2. Current number is within valid range [1, n]
13            // 3. Current number is not already at its correct position
14            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
15                // Swap current number to its correct position
16                swap(nums[i], nums[nums[i] - 1]);
17            }
18        }
19      
20        // Find the first position where the number doesn't match its expected value
21        for (int i = 0; i < n; ++i) {
22            // Position i should contain value i + 1
23            if (nums[i] != i + 1) {
24                return i + 1;  // Return the first missing positive
25            }
26        }
27      
28        // All positions [0, n-1] contain correct values [1, n]
29        // So the first missing positive is n + 1
30        return n + 1;
31    }
32};
33
1/**
2 * Finds the first missing positive integer in an array
3 * Uses cyclic sort to place each number at its correct index position
4 * Time complexity: O(n), Space complexity: O(1)
5 * 
6 * @param nums - Array of integers
7 * @returns The smallest missing positive integer
8 */
9function firstMissingPositive(nums: number[]): number {
10    const arrayLength: number = nums.length;
11  
12    // Step 1: Place each positive number at its correct index position
13    // Number 1 should be at index 0, number 2 at index 1, etc.
14    for (let currentIndex = 0; currentIndex < arrayLength; currentIndex++) {
15        // Keep swapping while:
16        // - Current number is in valid range [1, n]
17        // - Current number is not already at its correct position
18        while (nums[currentIndex] >= 1 && 
19               nums[currentIndex] <= arrayLength && 
20               nums[currentIndex] !== nums[nums[currentIndex] - 1]) {
21          
22            // Calculate target index for the current number
23            const targetIndex: number = nums[currentIndex] - 1;
24          
25            // Swap current number with the number at its target position
26            [nums[currentIndex], nums[targetIndex]] = [nums[targetIndex], nums[currentIndex]];
27        }
28    }
29  
30    // Step 2: Find the first position where number doesn't match (index + 1)
31    for (let index = 0; index < arrayLength; index++) {
32        // If number at index i is not (i + 1), then (i + 1) is missing
33        if (nums[index] !== index + 1) {
34            return index + 1;
35        }
36    }
37  
38    // Step 3: All numbers from 1 to n are present, so return n + 1
39    return arrayLength + 1;
40}
41

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array.

The algorithm consists of two main parts:

  1. The first loop with a nested while loop that rearranges elements to their correct positions. Although there's a while loop inside the for loop, each element is moved at most once to its correct position. Once an element is placed correctly (where nums[i] == i + 1), it won't be moved again. Therefore, the total number of swaps across all iterations is at most n, making this part O(n).

  2. The second loop simply iterates through the array once to find the first position where nums[i] != i + 1, which takes O(n) time.

Overall time complexity: O(n) + O(n) = O(n).

Space Complexity: O(1).

The algorithm only uses a constant amount of extra space:

  • Variables i, j, and n for iteration and indexing
  • The swapping operation is done in-place without requiring additional arrays or data structures

The input array is modified in-place, so no additional space proportional to the input size is used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Swap Implementation Leading to Infinite Loops

One of the most common mistakes is incorrectly implementing the swap logic, which can cause infinite loops when duplicates are present.

Incorrect Implementation:

while 1 <= nums[i] <= n:
    j = nums[i] - 1
    nums[i], nums[j] = nums[j], nums[i]

Why it fails: Without checking nums[i] != nums[nums[i] - 1], the code will infinitely swap when encountering duplicates. For example, with nums = [1, 1], position 0 will keep trying to swap 1 to position 0 (where it already is).

Correct Implementation:

while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
    j = nums[i] - 1
    nums[i], nums[j] = nums[j], nums[i]

2. Using Wrong Variable in Swap Operation

Another frequent error is accidentally using the loop index i instead of the calculated target index when swapping.

Incorrect Implementation:

while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
    nums[i], nums[i - 1] = nums[i - 1], nums[i]  # Wrong! Uses i-1 instead of nums[i]-1

Why it fails: This swaps with the wrong position. We need to swap with position nums[i] - 1, not i - 1.

Correct Implementation:

while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
    target = nums[i] - 1  # Store target index first
    nums[i], nums[target] = nums[target], nums[i]

3. Order of Operations in Swap Statement

The swap operation must be carefully written to avoid overwriting values before they're used.

Potentially Problematic Implementation:

while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
    nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]  # Dangerous ordering

Why it can fail: In some languages or Python implementations, the right side might not be fully evaluated before assignment begins. After nums[nums[i] - 1] is assigned, nums[i] changes, making the second nums[nums[i] - 1] reference incorrect.

Safe Implementation:

while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
    j = nums[i] - 1  # Calculate index first
    nums[i], nums[j] = nums[j], nums[i]  # Then swap

4. Using if Instead of while for Swapping

Incorrect Implementation:

for i in range(n):
    if 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
        j = nums[i] - 1
        nums[i], nums[j] = nums[j], nums[i]

Why it fails: After swapping, the new element at position i might also need to be moved to its correct position. Using if only performs one swap and moves on, leaving some elements in wrong positions.

Example where it fails: nums = [3, 1, 2]

  • At i=0: Swap 3 with element at index 2 → [2, 1, 3]
  • With if: Move to i=1, but 2 at index 0 is still wrong
  • With while: Continue swapping 2 to index 1 → [1, 2, 3]

Correct Implementation:

for i in range(n):
    while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
        j = nums[i] - 1
        nums[i], nums[j] = nums[j], nums[i]
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More