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.
This approach focuses on dividing the journey into two segments. The frog can travel a path by skipping certain stones while minimizing the maximum jump in both the forward and return trips. The frog can either move in order and then skip back for the shortest jump, skipping intermediate stones optimally, or follow an alternate path with strategic skips across stones.
The Python function min_jump_cost calculates the minimum cost by searching for the maximum gap when skipping an intermediate stone. We calculate the largest possible jump needed when skipping each intermediate stone, including the direct start-to-end connection and the smallest immediate connections on both ends.
Python
C++
Java
JavaScript
C#
Time Complexity: O(n), where n is the number of stones. The algorithm involves checking between all adjacent stones once.
Space Complexity: O(1), as it requires only constant extra space outside the input.
This approach uses dynamic programming to determine the minimal jump cost by considering all possible paths between stones. This involves using a memoization table to store and reuse calculations from previous steps.
The conceptual basis is to minimize the largest jump in any full round-trip path, adjusting calculations dynamically with each potential path resolution.
This dynamic programming solution in Python iteratively calculates minimal jump costs for each stone, adjusting based upon previous incremental costs while optimizing each step towards minimizing the maximal jump.
Python
C++
Java
JavaScript
C#
Time Complexity: O(n2) due to nested loops for path calculations.
Space Complexity: O(n) for storage of interim results.
| Approach | Complexity |
|---|---|
| Skipping Strategy using Two Segments | Time Complexity: O(n), where n is the number of stones. The algorithm involves checking between all adjacent stones once. |
| Dynamic Programming Approach | Time Complexity: O(n2) due to nested loops for path calculations. |
| Default Approach | — |
| 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. |
Frog Jump II - Greedy - Leetcode 2498 - Python • CheatCode Ninja • 5,948 views views
Watch 6 more video solutions →Practice Frog Jump II with our built-in code editor and test cases.
Practice on FleetCode