Show problems as
Classic problem #403HardArrayDynamic Programming

Frog Jump

Real-world version: Pipeline Pad Hops
Tracked in this browser only
Read Frog Jump on LeetCode(opens in a new tab)

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

An inspection crawler walks a pipeline by hopping between steel pads bolted to the outside of the pipe. pads lists the distance of each pad from the pump house in metres, sorted strictly increasing, and pads[0] is always 0 because the crawler is parked on the first pad.

Hops obey two rules:

  • The very first hop must cover exactly 1 metre.
  • If the crawler's previous hop covered k metres, its next hop must cover k - 1, k or k + 1 metres. A hop always moves forward, so its length must be at least 1 metre.

Every hop has to finish on a pad; landing on bare pipe is not allowed, and the crawler may not skip a hop or move backwards.

Return true if the crawler can get from the first pad to the last pad in pads, and false otherwise. Pads in between may be passed over.

Examples

Example 1

Input
pads = [0, 1, 2, 4, 7, 11]
Output
true

Hops of 1, 1, 2, 3 and 4 metres land on pads 1, 2, 4, 7 and 11. The first hop is 1 metre and every later hop is within 1 metre of the one before it.

Example 2

Input
pads = [0, 2]
Output
false

The opening hop has to cover exactly 1 metre, and there is no pad 1 metre along, so the crawler never leaves the first pad.

Example 3

Input
pads = [0, 1, 3, 6, 8]
Output
true

Hops of 1, 2, 3 and 2 metres land on pads 1, 3, 6 and 8. Each hop length is within 1 metre of the previous hop, and the 2-metre finish is one metre shorter than the 3-metre hop before it.

Example 4

Input
pads = [0, 1, 3, 6, 7]
Output
false

Pad 6 can only be entered with a 3-metre hop, after hops of 1 and 2 metres. A 3-metre hop must be followed by one of 2, 3 or 4 metres, which land on bare pipe at 8, 9 and 10, and pad 7 stays out of reach by every other legal sequence too.

Constraints

  • 2 <= pads.length <= 2000
  • 0 <= pads[i] <= 2^31 - 1
  • pads[0] == 0
  • pads is sorted in strictly increasing order.

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 can_reach_last_pad(pads: list[int]) -> bool:
Java
public boolean canReachLastPad(int[] pads)

More on the same topics