0204EasyArrayBinary Search

Kth Free Parking Bay

Tracked in this browser only

Trains the technique from

LeetCode 1539Kth Missing Positive Number

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 depot labels its parking bays 1, 2, 3 and onward, and the labelling never stops, so there is no highest bay. taken lists the bays already let out to tenants in strictly increasing order, which means no bay is listed twice. Any bay whose label does not appear in taken is free.

Given taken and an integer k, return the label of the k-th smallest free bay.

Free bays carry on past the largest label in taken, so the answer may well be larger than every entry in the list. Since taken arrives in order, aim for a running time of O(log n) in its length rather than reading every entry.

Examples

Example 1

Input: taken = [3, 4, 8, 9], k = 4
Output: 6

The free labels in order are 1, 2, 5, 6, 7, 10, and so on. The fourth of them is 6.

Example 2

Input: taken = [1, 2, 3], k = 5
Output: 8

Bays 1, 2 and 3 are let out, so the free labels start 4, 5, 6, 7, 8 and the fifth is 8.

Example 3

Input: taken = [6], k = 6
Output: 7

Only bay 6 is let out, so the free labels run 1, 2, 3, 4, 5, 7, and the sixth is 7.

Example 4

Input: taken = [9, 10, 11, 12, 13], k = 4
Output: 4

Nothing below 9 is let out, so the free labels begin 1, 2, 3, 4 and the fourth is 4.

Constraints

1 <= taken.length <= 1000
1 <= taken[i] <= 1000
1 <= k <= 1000
taken[i] < taken[j] for 1 <= i < j <= taken.length

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 kth_free_bay(taken: list[int], k: int) -> int:

Java

public int kthFreeBay(int[] taken, int k)

The intended approach

Time O(log n)Space O(1)

For the entry at position `i`, exactly `taken[i] - (i + 1)` labels below it are free, and that figure never drops as `i` grows. Binary search for the leftmost entry whose figure already reaches `k`; every entry left of it has fewer free labels beneath it, so the search settles on the number of let-out bays that sit below the answer. Adding `k` to that count gives the label, and the same sum is right when no entry reaches `k` and the answer lies beyond the whole list.

Pythonentry point: kth_free_bay

def kth_free_bay(taken, k):
    # Time O(log n): binary search over the allotted bays. Space O(1).
    lo = 0
    hi = len(taken) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        free_below = taken[mid] - (mid + 1)
        if free_below >= k:
            hi = mid - 1
        else:
            lo = mid + 1
    return lo + k

The obvious version

Put the let-out labels in a set and count upward from 1, tallying every label that is not in the set until the tally reaches k. Linear in the answer rather than logarithmic in the list.

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_kth_free_bay(taken, k):
    allotted = set(taken)
    seen = 0
    bay = 0
    while seen < k:
        bay += 1
        if bay not in allotted:
            seen += 1
    return bay

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
4 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