First Missing Positive hard

Problem Statement

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

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

Steps

The core idea is to utilize the array itself as a hash table. Since we're only interested in positive integers, we can use the array index to represent the number. If a number n is present, we can mark the index n-1 in a way that indicates its presence. We'll then iterate through the array again to find the first index that hasn't been marked, corresponding to the smallest missing positive integer.

Here's a breakdown of the steps:

1. Handle Negatives and Numbers Greater Than N: First, we'll remove any negative numbers and numbers greater than the array's length (n) because they are irrelevant to finding the smallest missing positive integer. We'll replace these numbers with 1. This is because we only care about the numbers from 1 to n.

2. Use the Array as a Hash Table: Iterate through the array. If the value nums[i] is positive and less than or equal to n, we use its absolute value (abs(nums[i])) to mark the corresponding index. We mark the index by negating the value at that index (if it's not already negative). This is a trick to avoid using extra space.

3. Find the Smallest Missing Positive: Iterate through the array again. The first index i where nums[i] is positive indicates that the number i+1 is missing.

Explanation

The algorithm leverages the fact that the smallest missing positive integer must be within the range [1, n+1], where n is the length of the input array. By using the array itself as a hash table, we avoid using extra space (except for a small constant amount). The negation trick allows us to efficiently mark the presence of numbers without needing extra data structures like a set or hash map.

Code

#include <vector>
#include <cmath>

using namespace std;

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

    // Step 1: Handle negatives and numbers > n
    for (int i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = 1;
        }
    }

    // Step 2: Use array as hash table
    for (int i = 0; i < n; i++) {
        int index = abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }

    // Step 3: Find the smallest missing positive
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }

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

Complexity

• Time Complexity: O(n). We iterate through the array three times, each time taking O(n) time.
• Space Complexity: O(1). We use constant extra space. The algorithm modifies the input array in place.