Watch 7 video solutions for Frog Jump II, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by CheatCode Ninja has 5,948 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array stones sorted in strictly increasing order representing the positions of stones in a river.
A frog, initially on the first stone, wants to travel to the last stone and then return to the first stone. However, it can jump to any stone at most once.
The length of a jump is the absolute difference between the position of the stone the frog is currently on and the position of the stone to which the frog jumps.
stones[i] and is jumping to stones[j], the length of the jump is |stones[i] - stones[j]|.The cost of a path is the maximum length of a jump among all jumps in the path.
Return the minimum cost of a path for the frog.
Example 1:
Input: stones = [0,2,5,6,7] Output: 5 Explanation: 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 Explanation: 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 <= 1050 <= stones[i] <= 109stones[0] == 0stones is sorted in a strictly increasing order.Problem Overview: You are given a sorted array of stone positions in a river. A frog must jump from the first stone to the last and then return to the start, visiting each stone at most once. The goal is to minimize the maximum jump distance made during the entire trip. The challenge is arranging the visiting order so the largest jump stays as small as possible.
Approach 1: Skipping Strategy using Two Segments (Greedy) (Time: O(n), Space: O(1))
The key observation is that visiting stones strictly in order creates large jumps on the return path. A better strategy splits stones into two alternating paths. The frog effectively jumps every other stone while going forward and uses the skipped stones on the way back. This pattern minimizes the largest gap encountered. Implementation becomes simple: iterate through the array and compute stones[i] - stones[i-2] for all i ≥ 2, tracking the maximum value. That value represents the worst jump the frog must make when using the optimal zigzag traversal. This works because alternating stones distributes the gaps more evenly across the route. The algorithm only scans the array once and uses constant extra memory, making it the optimal solution for this greedy pattern over a sorted array.
Approach 2: Dynamic Programming Approach (Time: O(n²), Space: O(n²))
A more explicit strategy models the order of visits using dynamic programming. Define states that track the minimum possible maximum jump after choosing certain stones for the forward path and leaving others for the return path. For each pair of stones, evaluate transitions that simulate choosing the next stone while updating the current worst jump distance. This approach systematically checks different distributions of stones between forward and backward paths. Although correct, the number of state transitions grows quickly, resulting in quadratic time and space complexity. This method helps understand the structure of the problem but is less practical for large inputs.
Some developers also reason about the answer using binary search on the maximum allowed jump and verifying feasibility. However, the greedy skipping insight eliminates the need for searching because the optimal pattern can be computed directly.
Recommended for interviews: The greedy skipping strategy is the expected solution. Interviewers want to see the insight that alternating stones minimizes the largest gap. A dynamic programming explanation shows deeper reasoning about path construction, but the O(n) greedy scan demonstrates strong pattern recognition and leads to the cleanest implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Skipping Strategy using Two Segments (Greedy) | O(n) | O(1) | Best choice for interviews and production. Uses the alternating stone insight to directly compute the minimal maximum jump. |
| Dynamic Programming | O(n²) | O(n²) | Useful for reasoning about different visit orders or when exploring state transitions during problem analysis. |