Coding - First Missing Positive

Full Interview Question: "Coding - First Missing Positive"

Problem Statement

You are given an unsorted array nums of n integers. Find the smallest missing positive integer in this array.

Examples

1. Input: nums = [1, 2, 0] Output: 3 Explanation: The first missing positive integer is 3.

2. Input: nums = [3, 4, -1, 1] Output: 2 Explanation: The first missing positive integer is 2.

3. Input: nums = [7, 8, 9, 11, 12] Output: 1 Explanation: The first missing positive integer is 1.

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1

Hints

1. Sorting Approach: You can sort the array first and then iterate through it to find the first missing positive integer. However, this approach has a time complexity of O(n log n) due to sorting.
2. Hash Map Approach: Use a hash map to store the presence of numbers in the array. Then, iterate through the numbers from 1 to n and check if any number is missing.
3. In-place Approach: Use the array itself to store the presence of numbers by marking the index i as negative if abs(nums[i]) is present in the array. Then, iterate through the array to find the first index i such that nums[i] is not marked as present.

Solution

Here's a Python solution using the in-place approach:

`python class Solution: def firstMissingPositive(self, nums): n = len(nums) for i in range(n): while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: # Swap nums[i] with nums[nums[i] - 1] nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1

`

This solution has a time complexity of O(n) and a space complexity of O(1).