Is First Missing Positive easy or hard?

First Missing Positive is classified as a Hard problem because it requires recognizing that the answer must lie in the range [1, n+1] and using that insight to design an in-place O(n) algorithm with constant extra space.

First Missing Positive Python/Java solution

Python and Java implementations typically follow the cyclic sort idea. Iterate through the array and swap elements until each valid value is placed at index value-1. Then perform a linear scan to find the first index where the expected value is missing.

How to solve First Missing Positive in O(n)?

Use index placement. Iterate through the array and swap numbers so each value x goes to position x-1 whenever 1 ≤ x ≤ n. After all valid numbers are placed, scan the array again; the first position where nums[i] is not equal to i+1 gives the missing positive integer.

What is the best approach for First Missing Positive?

The cyclic sort (index placement) approach is considered the best solution. It places each number x at index x-1 if it falls within the range [1, n]. After rearranging, the first index where nums[i] != i+1 reveals the missing positive. This runs in O(n) time and uses O(1) extra space.

Is First Missing Positive asked at Google/Amazon/Meta?

First Missing Positive frequently appears in interviews at large tech companies including Google, Amazon, and Meta. The problem tests in-place array manipulation, constraint reasoning, and the ability to achieve linear time with constant extra space.

What data structure is used in First Missing Positive?

The problem primarily uses array manipulation techniques. Some solutions rely on hash-style presence tracking with an auxiliary array, while the optimal approach treats the input array itself as a placement structure using cyclic swaps.

What is the time complexity of First Missing Positive?

The optimal solution runs in O(n) time with O(1) extra space using the cyclic sort technique. Alternative solutions include a hash-based presence array with O(n) time and O(n) space, or a sorting approach with O(n log n) time.

Description Hints 3 Solution Video 21:22

41. First Missing Positive

Hard43.8% acceptance33 companies

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

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

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Asked at top 20 of 33 companies

Myntra MakeMyTrip Netskope Harness Soundhound Zomato ServiceNow Amazon Walmart Labs Cognizant Tesla Sprinklr

+8 more

Swiggy Netflix Ola Geico

Google Microsoft Meta Oracle

Topics

Array Hash Table

Hints open one at a time

Hint 1

Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?

Hint 2

We don't care about duplicates or non-positive integers

Hint 3

Remember that O(2n) = O(n)

21:22

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution