Smallest Absent Positive

HardArrays & Hashing

Problem

A cloakroom hands out numbered tags starting from 1. The list nums holds the tag numbers currently in use, mixed with junk entries (zero, negatives, numbers far too large) from a faulty scanner. When a new guest arrives, they get the smallest positive tag number that is not in use.

Return the smallest positive integer that does not appear in nums. Your algorithm must run in O(n) time and use O(1) extra space; you may rearrange nums.

Example 1

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

1 and 2 are in use; 3 is free.

Example 2

Input:
nums = [7, 8, 9]
Output:
1

Example 3

Input:
nums = [1, 2, 3]
Output:
4

Constraints

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

Hint

Show the first hint

With n numbers, the answer is always between 1 and n + 1. Why?

Walkthrough

How to approach it

01Clarify before coding

  • May I modify the input? Yes, rearranging is allowed, which is what makes O(1) space possible.
  • Are duplicates possible? Yes; they must not cause infinite swapping.
  • What if 1..n are all present? Then the answer is n + 1.

02Brute force

Put all values in a hash set and test 1, 2, 3, … until one is missing; or sort and scan.

Cost: The set is O(n) time but O(n) extra space; sorting is O(n log n) time. Neither meets O(n) time with O(1) space.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.