LeetCode 2498 - Frog Jump II

The problem gives us a sorted array stones, where each value represents the position of a stone in a river. The frog starts on the first stone, which is always at position 0, and must travel to the last stone and then eventually return to the first stone.

leetcodemediumarraybinary-searchgreedy

LeetCode Problem 2498

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Greedy

Solution

Problem Understanding

The problem gives us a sorted array stones, where each value represents the position of a stone in a river. The frog starts on the first stone, which is always at position 0, and must travel to the last stone and then eventually return to the first stone.

The important restriction is that every stone can be visited at most once. This means the frog cannot reuse intermediate stones while going forward and backward. The only stones that may appear twice in the overall trip are the starting and ending stones, because the frog begins at one and must return there after reaching the other.

Each jump has a length equal to the absolute difference between the positions of two stones. The cost of an entire route is defined as the maximum jump length used anywhere in the trip. Our goal is to minimize this maximum jump.

In other words, we want to design a valid forward-and-back traversal such that the largest individual jump is as small as possible.

The constraints are important:

  • stones.length can be as large as 10^5
  • Stone positions can be up to 10^9
  • The array is strictly increasing

These constraints immediately rule out exponential or quadratic solutions. Any algorithm that explores many possible paths will be far too slow. We need a linear or near-linear approach.

A few edge cases stand out immediately:

  • If there are only two stones, the frog has no choice but to jump directly there and back.
  • Large gaps between stones can dominate the answer.
  • A naive greedy traversal may fail because using nearby stones on the forward trip may leave impossible large jumps for the return trip.
  • Since stones cannot be reused, we must carefully partition which stones are used on the outward journey and which are used on the return journey.

The strictly increasing order is also useful because it means all jumps are naturally between ordered positions, allowing us to reason about adjacent and alternating gaps.

Approaches

Brute Force Approach

A brute-force solution would attempt to generate all valid ways to split the stones between the forward path and the return path.

For every possible partition of intermediate stones, we could:

  1. Build the forward route from the first stone to the last stone.
  2. Build the return route using the remaining stones.
  3. Compute the maximum jump in the entire traversal.
  4. Track the minimum possible cost across all valid traversals.

This approach is correct because it examines every possible valid path configuration.

However, it is computationally infeasible. If there are n stones, each intermediate stone can effectively belong to either the outward path or the return path. That creates roughly 2^(n-2) possibilities. With n up to 100000, this is completely impossible.

We need a structural observation that eliminates the need to search.

Key Insight

The optimal strategy is to avoid consecutive usage of stones whenever possible.

Suppose we move through stones in an alternating pattern:

  • Forward trip uses stones at indices 0, 2, 4, ...
  • Return trip uses stones at indices ..., 5, 3, 1

This creates jumps between stones two indices apart.

The critical observation is that any valid traversal must eventually create jumps that skip over some stones, because stones cannot be reused on both trips. The best possible arrangement minimizes the largest such skipped jump.

It turns out the optimal answer is simply:

$$\max(stones[i] - stones[i-2])$$

for all i >= 2.

Intuitively, the alternating traversal spreads the jumps as evenly as possible. If we instead used consecutive stones too often in one direction, the opposite direction would be forced into larger jumps.

This leads to a very simple linear solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries every possible forward/return assignment
Optimal O(n) O(1) Uses the alternating-jump observation

Algorithm Walkthrough

Step 1: Initialize the answer

We begin with the smallest possible answer value.

Since the frog must at least jump between the first two stones in some scenarios, we can initialize using the first adjacent difference.

Step 2: Examine jumps between stones two indices apart

Starting from index 2, compute:

stones[i] - stones[i - 2]

This represents the jump created by the alternating traversal pattern.

We track the maximum such value because the total path cost is determined by the largest jump.

Step 3: Update the maximum jump

For every valid i, update:

answer = max(answer, stones[i] - stones[i - 2])

This ensures we capture the worst jump required by the optimal arrangement.

Step 4: Return the final answer

After scanning the array once, the stored maximum value is the minimum achievable path cost.

Why it works

The key invariant is that no stone can be reused on both the forward and return trips. Therefore, consecutive stones cannot all be traversed sequentially in both directions. At some point, the frog must skip stones.

The alternating traversal pattern minimizes the largest required skip. Any other arrangement would force some jump to be at least as large as one of the stones[i] - stones[i-2] gaps.

Thus, the maximum gap between stones two apart is both necessary and sufficient, proving the algorithm is optimal.

Python Solution

from typing import List

class Solution:
    def maxJump(self, stones: List[int]) -> int:
        n = len(stones)

        if n == 2:
            return stones[1] - stones[0]

        max_jump = stones[1] - stones[0]

        for i in range(2, n):
            max_jump = max(max_jump, stones[i] - stones[i - 2])

        return max_jump

The implementation directly follows the mathematical observation from the algorithm.

We first handle the smallest possible input size, where there are only two stones. In that situation, the frog must jump directly between them.

Next, we initialize max_jump using the first adjacent difference.

The loop starts at index 2 because we need to compare each stone with the stone two positions earlier. For every iteration, we compute the alternating jump distance and update the running maximum.

At the end, the largest such alternating gap is returned as the optimal cost.

The implementation runs in linear time and uses constant extra memory.

Go Solution

func maxJump(stones []int) int {
	n := len(stones)

	if n == 2 {
		return stones[1] - stones[0]
	}

	maxJumpValue := stones[1] - stones[0]

	for i := 2; i < n; i++ {
		jump := stones[i] - stones[i-2]

		if jump > maxJumpValue {
			maxJumpValue = jump
		}
	}

	return maxJumpValue
}

The Go implementation mirrors the Python solution closely.

Since Go does not provide a built-in max function for integers, we manually compare values with an if statement.

Integer overflow is not a concern because the maximum difference between stone positions is at most 10^9, which safely fits inside Go's int type on LeetCode environments.

Slices are used naturally for array access, and no additional memory allocation is required.

Worked Examples

Example 1

stones = [0,2,5,6,7]

We compute the maximum value of stones[i] - stones[i-2].

i stones[i] stones[i-2] Difference Current Maximum
2 5 0 5 5
3 6 2 4 5
4 7 5 2 5

Final answer:

5

An optimal traversal is:

0 -> 5 -> 7 -> 6 -> 2 -> 0

The jumps are:

5, 2, 1, 4, 2

The maximum jump is 5.

Example 2

stones = [0,3,9]

Compute alternating gaps:

i stones[i] stones[i-2] Difference Current Maximum
2 9 0 9 9

Final answer:

9

The frog must eventually make a jump of length 9, so the minimum possible cost is 9.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array
Space O(1) Only a few variables are used

The algorithm scans the array exactly once and performs constant-time work per iteration. No auxiliary data structures are needed, so the extra memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def maxJump(self, stones: List[int]) -> int:
        n = len(stones)

        if n == 2:
            return stones[1] - stones[0]

        max_jump = stones[1] - stones[0]

        for i in range(2, n):
            max_jump = max(max_jump, stones[i] - stones[i - 2])

        return max_jump

sol = Solution()

assert sol.maxJump([0, 2, 5, 6, 7]) == 5  # Provided example
assert sol.maxJump([0, 3, 9]) == 9  # Provided example

assert sol.maxJump([0, 1]) == 1  # Minimum input size
assert sol.maxJump([0, 1, 2]) == 2  # Simple three-stone case
assert sol.maxJump([0, 2, 4]) == 4  # Must jump directly eventually

assert sol.maxJump([0, 1, 3, 6, 10]) == 7  # Increasing gaps
assert sol.maxJump([0, 5, 6, 7, 8]) == 6  # Large first gap
assert sol.maxJump([0, 2, 4, 6, 8]) == 4  # Uniform spacing

assert sol.maxJump([0, 10, 20, 30, 40]) == 20  # Large equal gaps
assert sol.maxJump([0, 1, 100]) == 100  # Huge final jump

assert sol.maxJump([0, 2, 3, 5, 9]) == 6  # Mixed spacing
Test Why
[0,2,5,6,7] Validates the primary example
[0,3,9] Validates large mandatory jump
[0,1] Smallest valid input
[0,1,2] Minimal nontrivial traversal
[0,2,4] Requires direct return jump
[0,1,3,6,10] Tests growing gaps
[0,5,6,7,8] Large initial spacing
[0,2,4,6,8] Uniformly spaced stones
[0,10,20,30,40] Large equal intervals
[0,1,100] Extreme jump dominates answer
[0,2,3,5,9] Irregular spacing pattern

Edge Cases

One important edge case occurs when there are only two stones. In this situation, the frog has no flexibility at all. It must jump directly from the first stone to the last stone and then back again. A careless implementation might incorrectly assume there is always an index i-2 available. The implementation handles this explicitly with an early return.

Another important case is when one gap is dramatically larger than all others, such as [0,1,100]. Even though most jumps are tiny, the frog cannot avoid making a jump of length 100 at some point. The algorithm correctly captures this because the alternating gap computation naturally exposes unavoidable large skips.

Uniform spacing is also worth considering. For example, [0,2,4,6,8] may tempt someone into thinking the answer is 2, since adjacent stones differ by only 2. However, because stones cannot be reused, the frog must effectively alternate stones, producing jumps of size 4. The implementation correctly identifies this by checking gaps two indices apart.

A final subtle case involves odd versus even numbers of stones. The alternating traversal pattern behaves slightly differently depending on parity, but the mathematical observation still holds universally. Since the algorithm only relies on the maximum stones[i] - stones[i-2], it automatically handles both cases without special branching.