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 or numbers greater than the array's length. We'll use the array itself to mark which positive integers are present.

1. Handle edge cases: If the array is empty, the answer is 1.
2. Mark present numbers: Iterate through the array. If a number num is within the range [1, n] (where n is the array's length), we can use its absolute value as an index. If the element at that index is positive, we negate it to mark that number as present. We use absolute values to handle the case where a number might already be marked negative.
3. Find the missing number: Iterate through the array again. The index of the first positive number corresponds to the smallest missing positive integer.

Explanation

The algorithm cleverly uses the input array itself to store information about which positive integers are present. By negating elements at indices corresponding to present numbers, we avoid needing extra space. The final pass efficiently locates the first missing positive integer.

Code (C#)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int n = nums.Length;

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

        // Mark present numbers by negating elements at corresponding indices
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num > 0 && num <= n) {
                int index = num - 1;
                if (nums[index] > 0) {
                    nums[index] = -nums[index];
                }
            }
        }

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

        // If all numbers from 1 to n are present, the missing number is n + 1
        return n + 1;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array a constant number of times.
• Space Complexity: O(1). The algorithm uses constant extra space. We modify the input array in-place.