0119HardArrayHash Table

Smallest Free Bay Number

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def smallest_free_bay(labels: list[int]) -> int:

Java

public int smallestFreeBay(int[] labels)

The intended approach

Time O(n)Space O(1) beyond the input array, which is permuted in place

With `n` records the answer can only be a bay in `1..n+1`, so any entry outside that window is noise. Use the array as its own lookup table: for each position, keep swapping the entry it holds to the slot that entry belongs in (bay `v` belongs at index `v-1`) until the entry is out of range or its home slot already holds it, which also stops duplicates from cycling forever. Every swap parks one entry permanently, so the placement pass is linear overall; a second sweep returns the first index whose slot does not hold its own bay number, or `n+1` if all of them do.

Pythonentry point: smallest_free_bay

def smallest_free_bay(labels):
    n = len(labels)
    for i in range(n):
        while 1 <= labels[i] <= n and labels[labels[i] - 1] != labels[i]:
            home = labels[i] - 1
            labels[i], labels[home] = labels[home], labels[i]
    for i in range(n):
        if labels[i] != i + 1:
            return i + 1
    return n + 1

The obvious version

Dump every entry into a hash set, then try 1, 2, 3, ... until one is absent. Linear extra memory, which the statement forbids, but obviously correct.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_free_bay(labels):
    claimed = set(labels)
    bay = 1
    while bay in claimed:
        bay += 1
    return bay

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in