Show problems as
Classic problem #1539EasyArrayBinary Search

Kth Missing Positive Number

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

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

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

Python
def kth_free_bay(taken: list[int], k: int) -> int:
Java
public int kthFreeBay(int[] taken, int k)

More on the same topics