Ladder Gap Fillers

Medium

You stand on the floor (height 0) next to a ladder. The heights of its rungs are given by the strictly increasing list rungs, and you need to reach the top one. In one move you can climb to the next rung only if it is at most reach above where you are now (the floor or a rung). You may nail a new rung at any positive integer height that does not already have one. Return the smallest number of rungs you have to add to get to the top.

Example 1

rungs=[2, 4, 11], reach=3 → 2

The floor to 2 and 2 to 4 are within reach. Between 4 and 11 the gap is 7, so two new rungs are needed, say at 7 and 10.

Example 2

rungs=[5, 6, 7], reach=1 → 4

Each climb covers exactly one unit, so rungs at 1, 2, 3 and 4 are missing below the first one at height 5.

Example 3

rungs=[4, 8, 12], reach=4 → 0

Every gap is exactly 4, so nothing needs to be added.

Constraints

1 ≤ len(rungs) ≤ 10⁵
1 ≤ rungs[i] ≤ 10⁹
1 ≤ reach ≤ 10⁹
rungs is strictly increasing

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array

Similar problems

Two Boards Holding Water Medium Fewest Jumps to the End Medium Reach the Last Cell Medium As Many Trades as You Like Medium Where to Start the Lap Medium

Input

rungs=[2, 4, 11], reach=3

Expected

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