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 key idea is to use the array's indices as a hash table. Since we're only looking for the smallest missing positive integer, we can ignore any negative numbers and numbers greater than the array's length. We'll use the index i to represent the number i + 1. If nums[i] is within the valid range (1 to n, where n is the array's length), we'll mark its presence by making the element at index nums[i] - 1 negative. After iterating through the array, we'll scan for the first non-negative element. Its index plus 1 will be the smallest missing positive integer.

Explanation

1. Handle Invalid Inputs: If the array is empty, the smallest missing positive integer is 1.

2. Mark Present Numbers: Iterate through the array. For each positive number num within the range [1, n] (where n is the length of nums), if nums[num - 1] is positive, we change its sign to negative. This marks that the number num is present in the array. We use the index num - 1 because we're using 0-based indexing, but we're representing the number num.

3. Find the Missing Number: After marking, iterate through the array again. The index of the first positive number represents the smallest missing positive integer (remember to add 1 because of 0-based indexing).

4. Handle Edge Case: If all numbers from 1 to n are present, the smallest missing positive integer will be n + 1.

Code (TypeScript)

function firstMissingPositive(nums: number[]): number {
    const n = nums.length;

    // Handle empty array
    if (n === 0) return 1;

    // Mark numbers present in the array
    for (let i = 0; i < n; i++) {
        const num = nums[i];
        if (num > 0 && num <= n) {
            const index = num - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
    }

    // Find the first positive number
    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }

    // Handle case where all numbers from 1 to n are present
    return n + 1;
};

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array at most twice.
• Space Complexity: O(1). We modify the input array in-place; no extra space is used that scales with the input size.