First Missing Positive

Given an unsorted integer array nums, find the smallest missing positive integer.

Sample Input and Expected Output:

Input:

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

Output:

The smallest missing positive integer is: 2

Input:

nums = [1, 2, 0]

Output:

The smallest missing positive integer is: 3

First Missing Positive Solution in C++:

The idea is to use the array itself as a hash table. We want to place each positive integer x in the array at its correct position x-1, as the smallest missing positive integer will be in the range [1, n+1], where n is the size of the array. First, we ignore all non-positive integers and numbers greater than n. Then, for each positive integer x, we swap it with the number at position x-1 if x is within the valid range and not already at its correct position. After processing all numbers, we find the first index i such that nums[i] != i+1, and the smallest missing positive integer is i+1.

#include <iostream>
#include <vector>

int firstMissingPositive(std::vector<int>& nums) {
    int n = nums.size();

    // Step 1: Ignore non-positive integers and numbers greater than n.
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            std::swap(nums[i], nums[nums[i] - 1]);
        }
    }

    // Step 2: Find the first index i such that nums[i] != i+1.
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    // If all numbers from 1 to n are present, return n+1.
    return n + 1;
}

int main() {
    std::vector<int> nums1 = {3, 4, -1, 1};
    std::vector<int> nums2 = {1, 2, 0};

    int result1 = firstMissingPositive(nums1);
    int result2 = firstMissingPositive(nums2);

    std::cout << "The smallest missing positive integer is: " << result1 << std::endl;
    std::cout << "The smallest missing positive integer is: " << result2 << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the input vector nums. In the worst case, we might have to swap every number to its correct position, but each number is processed only once.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The algorithm is performed in-place without using any extra data structures.