Show problems as
Classic problem #41HardArrayHash Table

First Missing Positive

Real-world version: Smallest Free Bay Number
Tracked in this browser only
Read First Missing Positive on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A parking operator is migrating off an ancient permit system. The dump arrives as the array labels, one entry per surviving record, and nobody ever cleaned it: a record may hold a genuine bay number, a negative placeholder the old software wrote for cancelled permits, or a zero left behind by a half-finished write. Entries span the whole signed 32-bit range and the same bay may appear on several records.

Bays are numbered 1, 2, 3, and upward with no gaps in the physical lot. Report the lowest bay number that no record in the dump claims.

The dump is large, so your routine must run in time proportional to the number of records and may keep only a constant amount of extra room beyond the input. You may reorder the entries of labels in place and use the array itself as scratch space.

Examples

Example 1

Input
labels = [4, 1, 2, 6]
Output
3

Bays 1, 2, 4 and 6 are claimed. Bay 3 is the first one nobody holds, and the gap at 5 sits above it.

Example 2

Input
labels = [-8, 5, -3]
Output
1

Two records are cancelled placeholders and the only real claim is bay 5, so the very first bay is still free.

Example 3

Input
labels = [3, 2, 1]
Output
4

Every bay from 1 through 3 is taken, so the answer is one past the number of records.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def smallest_free_bay(labels: list[int]) -> int:
Java
public int smallestFreeBay(int[] labels)

More on the same topics