Free Stretches

Easy

Seats in a hall are numbered with the integers low through high inclusive. The occupied seats are listed in taken, which is sorted ascending, has no repeats and stays within those bounds. Return the free seats as the fewest possible ranges [a, b] (seats a through b inclusive). The ranges must be in ascending order, must not touch any occupied seat, and together must cover every free seat.

Example 1

taken=[3, 4, 9], low=1, high=12 → [[1, 2], [5, 8], [10, 12]]

The free numbers are 1–2, 5–8 and 10–12.

Example 2

taken=[], low=-5, high=5 → [[-5, 5]]

Nothing is taken, so the whole range is one stretch.

Example 3

taken=[6, 7, 8], low=6, high=8 → []

Everything is taken, so there are no free stretches.

Constraints

-10⁹ ≤ low ≤ high ≤ 10⁹
0 ≤ len(taken) ≤ 100
low ≤ taken[i] ≤ high
taken is strictly increasing

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array

Similar problems

Pair With a Target Sum Easy Squeeze Repeats Out of a Sorted Array Easy Drop the Unwanted Value Easy Slot on a Sorted Shelf Easy Add One to a Digit Array Easy

Input

taken=[3, 4, 9], low=1, high=12

Expected

[[1, 2], [5, 8], [10, 12]]

Run checks the first 3 tests in your browser. Submit checks all 122 tests on the server, hidden ones included.