We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

First Missing Positive

Number: 41

Difficulty: Hard

Paid? No

Companies: Amazon, Google, Microsoft, Netflix, Meta, Bloomberg, Oracle, Nutanix, Myntra, MakeMyTrip, Walmart Labs, Goldman Sachs, ServiceNow, SoundHound, Sprinklr, Zomato, Apple, Adobe, Morgan Stanley, Databricks, Uber, eBay, PayPal, TikTok, Siemens, General Motors, Roblox

Problem Description

Given an unsorted integer array nums, return the smallest positive integer that is not present in the array. The solution must run in O(n) time and use O(1) auxiliary space.

Key Insights

  • The missing positive number must be in the range [1, n+1] where n is the length of the array.
  • Use the array indices to place numbers in their correct positions (i.e., number i should be at index i-1) with in-place swapping.
  • After rearrangement, scan the array: the first index where the number is not equal to index+1 indicates the missing positive integer.

Space and Time Complexity

Time Complexity: O(n) as each number is swapped at most once. Space Complexity: O(1) since the rearrangement occurs in-place.

Solution

The approach involves reordering the array so that each positive integer in the range [1, n] is placed at the index corresponding to its value minus one. This means for any valid number i, nums[i-1] should be i. We iterate through the array and perform in-place swaps to achieve this order. After this process, another pass through the array reveals the first position where the number does not match the expected value (i+1), which is the smallest missing positive. If every position is correct, then the missing value is n+1.

Code Solutions

# Python implementation of First Missing Positive

def firstMissingPositive(nums):
    n = len(nums)
    # Rearrange numbers to their correct positions
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            correct_index = nums[i] - 1
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
    
    # Identify the first missing positive integer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

# Example usage:
print(firstMissingPositive([3, 4, -1, 1]))  # Output should be 2
← Back to All Questions