Stepping Pad Reachability
Problem
A garden path is a row of stepping pads. From pad i you may jump forward to any pad i + 1 up to i + pads[i] (a value of 0 means you are stuck on that pad).
You start on pad 0. Return true if you can reach the last pad.
Example 1
- Input:
- pads = [2, 0, 3, 0, 1]
- Output:
- true
0 → 2 → 4 (or 0 → 2 → 3 → 4).
Example 2
- Input:
- pads = [3, 2, 1, 0, 4]
- Output:
- false
Every route lands on pad 3, which has range 0.
Constraints
- 1 ≤ pads.length ≤ 1000
- 0 ≤ pads[i] ≤ 1000
Hint
Show the first hint
Ask the question per pad: from pad i, can I finish?
Walkthrough
How to approach it
01Clarify before coding
- Is starting on the last pad a success? Yes: a single pad means you are already there.
- Must I land exactly on the last pad, or can I overshoot? Jumps go to pads within range, and any jump past the end is not needed: reaching the last pad is enough.
- Can ranges be 0? Yes, those pads are dead ends unless they are the last pad.
02Brute force
Recursively try every jump length from the current pad (DFS without memory).
Cost: Exponential: the same pad is re-explored through every route that reaches it.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.