41. First Missing Positive

HardArrayHash Table
Leetcode Link

Problem Description

The LeetCode problem asks for the smallest missing positive integer from an unsorted integer array nums. The challenge is to write an algorithm that can find this number efficiently, with the constraint that the algorithm should have a time complexity of O(n) and a space complexity of O(1), which means the solution must run in linear time and use a constant amount of extra space.

Intuition

The intuition behind the solution comes from the realization that the smallest missing positive integer must be within the range [1, n+1], where n is the length of the array. This is because, in the worst case, the array contains all consecutive positive integers from 1 to n. Hence, the smallest missing positive integer would be just outside this range, which is n + 1.

To find this number within the given constraints, we apply the concept of placing each number in its 'correct position'. If nums contains a number x where 1 <= x <= n, x should be placed at index x-1. By swapping elements to their correct positions (when they are not already there), we aim to have an array where the element at each index i is equal to i + 1.

Once the placement process is complete, we perform a final linear scan. If we find an index i where nums[i] is not equal to i + 1, then i + 1 is our missing positive, as the number i + 1 is not in its correct position (which would be the index i). If all elements are in their correct positions, it means our array contains all numbers from 1 to n, so the smallest missing positive integer is n + 1.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The implementation of the solution leverages the fact that we only care about positive integers up to n, the length of the array. The key operations are swaps and a final scan to identify which positive integer is missing.

Here’s a step-by-step breakdown:

  1. Iterate through the array (nums), and for each element, perform the following actions:
    • Check if the current element is a positive integer and it’s within the range [1, n].
    • Ensure that it is not already in the correct position (meaning the element at the index nums[i] - 1 should be nums[i] itself).
  2. If an element meets the above criteria, swap it with the element at its “correct” position (the position it would have if all the elements [1, n] were sorted), which is index nums[i] - 1. This is done using the helper function swap(i, j).
  3. Repeat the process until the current element is out of range or already in the correct position.
  4. After the swapping loop, the array is scanned again from the beginning to find the first index i where nums[i] is not equal to i + 1. This index i indicates that i + 1 is the smallest missing positive integer because all the integers before i + 1 are already in their correct positions, and i + 1 is the first one that is missing from its correct position.
  5. If no such index i is found, it means all integers from 1 to n are present and in their correct positions, so the smallest missing positive integer is n + 1.

The algorithm employs the input array itself as the data structure to store information, which is why it’s able to achieve O(1) auxiliary space complexity, while still keeping the time complexity at O(n) due to the linear number of operations performed.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's take an example array to illustrate the solution approach: nums = [3, 4, -1, 1].

  1. We start by iterating through the array. The length of the array n = 4.

  2. The first element nums[0] is 3, which is a positive integer and within the range [1, n]. The correct position for 3 is at index 2 (3 - 1 = 2). Since nums[2] is -1, we swap nums[0] with nums[2]. Now the array looks like this: nums = [-1, 4, 3, 1].

  3. Next, we look at the element in the current index 0 which is now -1. Since -1 is negative and not in the range [1, n], we move to the next index.

  4. At index 1, the element is 4, which is greater than n and does not need to be placed within the range [1, n]. So we move on.

  5. At index 2, the element is 3 and is already in its correct position (index 2 + 1 = 3), so we move forward.

  6. At index 3, we have the number 1, which should be at index 0 (1 - 1 = 0). We swap nums[3] with nums[0]. The array now becomes: nums = [1, 4, 3, -1].

  7. At this point, we have iterated through the entire array, placing all positive integers within the range [1, n] in their correct positions.

  8. We now perform a final scan through the array. At index 0, we have nums[0] = 1, which is the correct placement.

  9. At index 1, we should have 2, but instead, we have nums[1] = 4. This tells us that 2 is the smallest missing positive integer because it is not at its correct position—which would be index 1.

  10. We conclude that 2 is the smallest missing positive integer in the array nums.

The array after processing is nums = [1, 4, 3, -1], and the smallest missing positive integer is 2.

Solution Implementation

1class Solution:
2    def firstMissingPositive(self, nums: List[int]) -> int:
3        # Function to swap elements at indices i and j
4        def swap_elements(index1, index2):
5            nums[index1], nums[index2] = nums[index2], nums[index1]
6
7        # Get the length of the list
8        list_length = len(nums)
9      
10        # Iterating through the list to place numbers on their correct positions
11        for i in range(list_length):
12            # Continuously swap the current element until it's in its correct position
13            # or it's out of range [1, n]
14            while 1 <= nums[i] <= list_length and nums[i] != nums[nums[i] - 1]:
15                swap_elements(i, nums[i] - 1)
16              
17        # After placing each element in its correct position, or as correct as possible, 
18        # traverse the list to find the first missing positive integer
19        for i in range(list_length):
20            # If the current number isn't the right number at index i, return i + 1,
21            # because it is the first missing positive integer
22            if i + 1 != nums[i]:
23                return i + 1
24      
25        # If all previous positions contain the correct integers, 
26        # then the first missing positive integer is n + 1 
27        return list_length + 1
28
1class Solution {
2    public int firstMissingPositive(int[] nums) {
3        int size = nums.length;
4
5        // Iterate over the array elements.
6        for (int i = 0; i < size; ++i) {
7            // While the current number is in the range [1, size] and it is not in the correct position
8            // (Which means nums[i] does not equal to nums[nums[i] - 1])
9            while (nums[i] > 0 && nums[i] <= size && nums[i] != nums[nums[i] - 1]) {
10                // Swap nums[i] with nums[nums[i] - 1] 
11                // The goal is to place each number in its corresponding index based on its value.
12                swap(nums, i, nums[i] - 1);
13            }
14        }
15
16        // Now that nums is reorganized, loop through the array
17        // to find the first missing positive number.
18        for (int i = 0; i < size; ++i) {
19            // If the number doesn't match its index (+1 because we are looking for positive numbers),
20            // that index (+1) is the first missing positive number.
21            if (nums[i] != i + 1) {
22                return i + 1;
23            }
24        }
25
26        // If no missing number found within [1, size], return size + 1 as the first missing positive number
27        return size + 1;
28    }
29
30    // Helper method to swap two elements in an array
31    private void swap(int[] nums, int firstIndex, int secondIndex) {
32        int temp = nums[firstIndex];
33        nums[firstIndex] = nums[secondIndex];
34        nums[secondIndex] = temp;
35    }
36}
37
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // Function to find the first missing positive integer in an array.
7    int firstMissingPositive(vector<int>& nums) {
8        int size = nums.size(); // Get the size of the array
9      
10        // Process each element in the array
11        for (int i = 0; i < size; ++i) {
12            // Continue swapping elements until the current element is out of bounds
13            // or it is in the correct position (value at index i should be i + 1)
14            while (nums[i] >= 1 && nums[i] <= size && nums[nums[i] - 1] != nums[i]) {
15                // Swap the current element to its correct position
16                swap(nums[i], nums[nums[i] - 1]);
17            }
18        }
19      
20        // After rearranging, find the first position where the index does not match the value
21        for (int i = 0; i < size; ++i) {
22            if (nums[i] != i + 1) {
23                // If such a position is found, the missing integer is i + 1
24                return i + 1;
25            }
26        }
27      
28        // If all positions match, the missing integer is size + 1
29        return size + 1;
30    }
31
32private:
33    // Helper function to swap two elements in the array
34    void swap(int& a, int& b) {
35        int temp = a;
36        a = b;
37        b = temp;
38    }
39};
40
1function firstMissingPositive(nums: number[]): number {
2    const size = nums.length; // Store the length of the array
3
4    // Iterate over the array to place each number in its correct position if possible
5    for (let currentIndex = 0; currentIndex < size; currentIndex++) {
6        // Calculate the target position for the current number
7        const targetIndex = nums[currentIndex] - 1;
8
9        // While the current number is in the range of the array indices,
10        // is not in its target position, and is not a duplicate,
11        // swap it with the number at its target position
12        while (
13            nums[currentIndex] > 0 &&
14            nums[currentIndex] <= size &&
15            nums[currentIndex] !== nums[targetIndex] &&
16            currentIndex !== targetIndex
17        ) {
18            // Swap the current number with the number at its target index
19            [nums[currentIndex], nums[targetIndex]] = [nums[targetIndex], nums[currentIndex]];
20            // Update the target index based on the new number at the current index
21            targetIndex = nums[currentIndex] - 1;
22        }
23    }
24
25    // After reordering, find the first number that is not at its correct index
26    // The index + 1 gives the missing positive integer
27    for (let index = 0; index < size; index++) {
28        if (nums[index] !== index + 1) {
29            return index + 1; // +1 to convert index to positive integer
30        }
31    }
32
33    // If all numbers are at their correct indices, then return the size + 1
34    return size + 1;
35}
36
Not Sure What to Study? Take the 2-min Quiz：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), which is linear with respect to the number of elements in the array nums. Within the first for loop, each element in nums that is within the range [1, n] is potentially swapped to its corresponding position (where the value v should be at index v - 1). Even though there is a while loop inside the for loop, each element can be swapped at most once because once an element is in its correct position, it no longer satisfies the while loop condition. Since each element is swapped at most once, the series of swaps can be considered to have a complexity of O(n).

After that, a second for loop runs which again is of complexity O(n). This loop does not contain any other loops or operations that would increase the time complexity. Therefore, considering both loops, the time complexity remains O(n).

Space Complexity

The space complexity of the code is O(1), which is constant space because the code only uses a fixed number of extra variables (for the swap function and for iterating over the elements of the array). The swaps are done in place and do not require any additional space that scales with the input size.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

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 algomonster s3 us east 2 amazonaws com recursion jpg You first

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫