0905MediumArrayDynamic Programming

Most Stones on the Way Across

Tracked in this browser only

Trains the technique from

LeetCode 2770Maximum Number of Jumps to Reach the Last Index

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Stepping stones sit in a line with heights nums. From the stone at position i you may step forward to any stone at a later position j whose height differs from nums[i] by at most target, in either direction.

You start on the first stone. Return the largest number of steps a crossing can take to reach the last stone, or -1 when the last stone cannot be reached at all.

Examples

Example 1

Input: nums = [4, 11, 6, 13, 9, 16], target = 5
Output: -1

Stepping 4 to 6 to 9 to 13 to 16 keeps every height change inside five and uses four steps, and no crossing manages more.

Example 2

Input: nums = [7, 7, 7, 7, 7], target = 0
Output: 4

Every stone is the same height, so every step is allowed and the crossing can take them one at a time.

Example 3

Input: nums = [1, 3, 6, 4, 1, 2], target = 0
Output: -1

With no allowance a step needs two stones of equal height, and no such step reaches the last stone.

Constraints

2 <= nums.length <= 1000
-10^9 <= nums[i] <= 10^9
0 <= target <= 2 * 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def maximum_jumps(nums: list[int], target: int) -> int:

Java

public int maximumJumps(int[] nums, int target)

The intended approach

Time O(n^2) for n stones: each stone looks back over the ones before it.Space O(n) for the per-stone counts.

A crossing only ever moves forward, so the best crossing to a stone is settled once the best crossing to every earlier stone is known. Hold, for each stone, the largest number of steps that reaches it, marking a stone unreachable until something reaches it. Sweep the stones in order and, for each one, look back over the earlier stones: any reachable earlier stone within the height allowance offers its own count plus one, and the largest such offer is the answer for this stone. The last stone's count is the answer, and an unreachable last stone gives -1. The sweep must skip earlier stones that are themselves unreachable, since stepping off a stone you could never stand on is not a crossing.

Pythonentry point: maximum_jumps

def maximum_jumps(nums, target):
    n = len(nums)
    steps = [-1] * n
    steps[0] = 0
    for i in range(1, n):
        for j in range(i):
            if steps[j] < 0:
                continue
            gap = nums[i] - nums[j]
            if gap < 0:
                gap = -gap
            if gap <= target and steps[j] + 1 > steps[i]:
                steps[i] = steps[j] + 1
    return steps[n - 1]

The obvious version

Walk out every crossing there is, stone by stone, and keep the longest one that lands on the last stone. Exponential in the stone count and it remembers nothing between crossings.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_maximum_jumps(nums, target):
    n = len(nums)
    best = [-1]

    def walk(at, taken):
        if at == n - 1:
            if taken > best[0]:
                best[0] = taken
            return
        for nxt in range(at + 1, n):
            gap = nums[nxt] - nums[at]
            if gap < 0:
                gap = -gap
            if gap <= target:
                walk(nxt, taken + 1)

    walk(0, 0)
    return best[0]

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in