Can You Reach the Last Stone

MediumGreedy

Problem

Stepping stones cross a river in a line. Standing on stone i, you can leap forward to any stone from i + 1 up to i + leaps[i] (a value of 0 means you are stuck there).

You start on stone 0. Return true if you can reach the last stone, false otherwise.

Example 1

Input:
leaps = [2, 3, 1, 1, 4]
Output:
true

Leap 0 → 1, then 1 → 4.

Example 2

Input:
leaps = [3, 2, 1, 0, 4]
Output:
false

Every route lands on stone 3, whose leap is 0, and no stone reaches beyond it.

Constraints

  • 1 ≤ leaps.length ≤ 10^5
  • 0 ≤ leaps[i] ≤ 10^5

Hint

Show the first hint

Instead of tracking every route, what single number describes everything you can reach so far?

Walkthrough

How to approach it

01Clarify before coding

  • Is leaps[i] the exact or the maximum leap? The maximum: any shorter leap is allowed.
  • Is a single stone already reached? Yes, you start on the last stone, so true.
  • Can leaps overshoot the end? Yes, overshooting is fine for reachability.

02Brute force

DFS or DP: canReach[i] is true if some earlier reachable j has j + leaps[j] ≥ i.

Cost: O(n · max leap) or O(n²) in the worst case, around 10^10 steps here.

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.

Solve it in the browserStart free

This problem is part of Pro.