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 looking for the smallest positive missing integer, we can ignore any negative numbers and numbers greater than the array's length. We'll use the array's indices to represent numbers. If we find a number num, we'll mark its index num - 1 with a negative value (or any marker that indicates its presence). After this process, the first index with a positive value corresponds to the smallest missing positive integer.

Explanation

1. Handle edge cases: If the array is empty, the smallest missing positive is 1.
2. Mark present numbers: Iterate through the array. If a number num is within the range [1, n] (where n is the length of the array), and the value at index num - 1 is positive, change the value at num - 1 to negative. We use negative values to mark that the number num exists. This step essentially uses the array as a hash table, where the index represents the number and the sign represents presence/absence.
3. Find the smallest missing: Iterate through the array again. The first index with a positive value indicates the smallest missing positive integer. If all are negative or we've reached the end of the array, the smallest missing positive is n + 1.

Code

def firstMissingPositive(nums):
    """
    Finds the smallest missing positive integer in an unsorted array.

    Args:
      nums: A list of integers.

    Returns:
      The smallest missing positive integer.
    """
    n = len(nums)
    if not nums:  #Handle empty array
        return 1

    # Mark present numbers by making corresponding index negative
    for i in range(n):
        num = nums[i]
        if 1 <= num <= n:
            index = num - 1
            if nums[index] > 0:
                nums[index] *= -1

    # Find the first positive index
    for i in range(n):
        if nums[i] > 0:
            return i + 1
    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 additional data structures are used that scale with input size. The space used is constant regardless of input size.