#2498

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Frog Jump II

Frog Jump II requires finding the minimal maximum jump length for a frog to traverse stones forward and backward efficiently.

array binary search greedy

Problem Statement

You are given a 0-indexed array stones representing positions of stones in a river in strictly increasing order. A frog starts on the first stone and wants to reach the last stone, jumping forward and backward, visiting each stone at most once.

Each jump has a length equal to the absolute difference between the current stone and the target stone. Determine the minimal possible maximum jump the frog must make to complete the round trip, ensuring no stone is used more than once.

Examples

Example 1

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

Output: 5

The above figure represents one of the optimal paths the frog can take. The cost of this path is 5, which is the maximum length of a jump. Since it is not possible to achieve a cost of less than 5, we return it.

Example 2

Input: stones = [0,3,9]

Output: 9

The frog can jump directly to the last stone and come back to the first stone. In this case, the length of each jump will be 9. The cost for the path will be max(9, 9) = 9. It can be shown that this is the minimum achievable cost.

Constraints

2 <= stones.length <= 105
0 <= stones[i] <= 109
stones[0] == 0
stones is sorted in a strictly increasing order.

Solution Approach

Binary Search on Maximum Jump

Perform binary search over the range of possible jump lengths. For each candidate maximum jump, check if a complete forward and backward traversal is possible. Narrow the search space until finding the minimal valid maximum jump.

Greedy Traversal Check

Simulate the frog's path greedily by always jumping to the next stone within the candidate maximum jump. Track the jumps for both forward and return trips. If any jump exceeds the candidate, the attempt fails.

Optimization and Edge Cases

Consider edge cases where stones are sparse or the first jump itself exceeds candidates. Use the array structure to skip unnecessary checks and ensure time efficiency, combining binary search with greedy validation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log D), where D is the range between the first and last stone, as binary search tests each jump length and each check traverses all stones. Space complexity is O(1) extra beyond the input array.

What Interviewers Usually Probe

Focus on validating jump lengths efficiently rather than enumerating all paths.
Expect discussion on greedy verification within the binary search loop.
Look for handling of edge jumps and minimal maximum logic in your solution.

Common Pitfalls or Variants

Common pitfalls

Assuming jumps can reuse stones, violating the problem constraint.
Failing to correctly simulate the return path, leading to underestimated jumps.
Mismanaging binary search bounds, which can skip the true minimal maximum.

Follow-up variants

Frog Jump with a single forward trip only, changing the binary search constraints.
Allow revisiting stones, which changes the greedy check strategy.
Frog Jump with variable energy limits, introducing dynamic programming options.

FAQ

What is the main pattern to use in Frog Jump II?

Binary search over the valid answer space is the core pattern to minimize the maximum jump length.

Can the frog jump to the same stone more than once?

No, each stone can be visited at most once, including during the return trip.

How do I verify a candidate maximum jump?

Use a greedy traversal to simulate jumps forward and backward, ensuring no jump exceeds the candidate.

What if the stones array has large gaps?

Binary search will still identify the minimal maximum jump, but the greedy check may fail for large candidates.

What is the time complexity of the solution?

O(n log D), where n is the number of stones and D is the distance between the first and last stone.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

class Solution:
    def maxJump(self, stones: List[int]) -> int:
        ans = stones[1] - stones[0]
        for i in range(2, len(stones)):
            ans = max(ans, stones[i] - stones[i - 2])
        return ans

Continue Practicing

#2517 maximum tastiness of candy basket #2528 maximize the minimum powered city #2448 minimum cost to make array equal