DevOps NetworkDevOpsNetwork
Join Free
Advanced

First Missing Positive

hardHard arrays and strings

Problem statement

You get an unsorted list of integers nums, which may contain zeros, negatives and duplicates. Return the smallest positive integer (1, 2, 3, ...) that does not appear in it.

A natural framing: nums are the worker IDs currently in use, and you want the lowest free ID to hand out next.

The challenge is the limit the problem sets: O(n) time and only O(1) extra memory. Sorting is too slow and a hash set uses too much memory, although both are fine as warm-ups.

Examples

Example 1

Input: nums = [5,1,2,-3,2]

Output: 3

Explanation: 1 and 2 are present; 3 is the first gap. 5, the duplicate 2 and -3 don't matter.

Example 2

Input: nums = [2,3,4]

Output: 1

Explanation: 1 itself is missing.

Hints

Approach

Cyclic placement: use the array as its own hash table. Only values 1..n matter, and value v belongs in index v - 1.

For each index i, while nums[i] is in 1..n and is not already in its home slot (nums[nums[i] - 1] != nums[i]), swap it into its home. Each swap puts at least one value in its final place, so there are at most n swaps in total. The second condition also stops infinite loops on duplicates.

Then scan once more: the first index i with nums[i] != i + 1 means i + 1 is missing. If every slot is correct, the answer is n + 1. This rearranges the input in place.

ComplexityTime O(n)Space O(1)
Python
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
home = nums[i] - 1
nums[i], nums[home] = nums[home], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
print(first_missing_positive([5, 1, 2, -3, 2]))
print(first_missing_positive([2, 3, 4]))

Follow-up questions

  • Do it without modifying the input. (Then you need O(n) memory, or a sort on a copy.)
  • Return the k smallest missing positives.

Frequently asked questions

Allocating the lowest free identifier is a real task: worker or shard IDs, the next free port in a range, the next free index for a disk device. The problem itself is mainly used in harder loops to test whether you can meet a strict memory limit by reusing the input array as storage.

There are only n numbers. For the answer to be larger than n + 1, all of 1 through n + 1 would have to be present, which needs n + 1 distinct values. So some value in 1..n+1 must be missing.

Every swap moves one value into its home slot, where it stays; a value already at home is never swapped again. There are at most n such values, so across the whole outer loop there are at most n swaps.