Skip to main content
Talentd

Frog Jump II - Solution & Explanation

MediumArrayBinary SearchGreedy11 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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.

  • More formally, if the frog is at 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 <= 105
  • 0 <= stones[i] <= 109
  • stones[0] == 0
  • stones is sorted in a strictly increasing order.

Approach Overview

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 1: Skipping Strategy using Two Segments

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.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

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.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

Time Complexity: O(n2) due to nested loops for path calculations.
Space Complexity: O(n) for storage of interim results.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), as it requires only constant extra space outside the input.

Dynamic Programming Approach

Time Complexity: O(n2) due to nested loops for path calculations.
Space Complexity: O(n) for storage of interim results.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 ProgrammingO(n²)O(n²)Useful for reasoning about different visit orders or when exploring state transitions during problem analysis.

Video Solution

Frog Jump II - Greedy - Leetcode 2498 - Python • CheatCode Ninja • 6,627 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Frog Jump II easy or hard?
Frog Jump II is considered a Medium difficulty problem. The implementation is straightforward once you recognize the alternating stone pattern, but identifying the greedy insight that minimizes the maximum jump can take some reasoning.
Frog Jump II Python/Java solution
In both Python and Java, the solution iterates through the array starting from index 2 and computes stones[i] - stones[i-2]. Maintain a variable tracking the maximum difference encountered. The final value is the minimal possible maximum jump distance for the round trip.
How to solve Frog Jump II in O(n)?
Iterate through the stone positions and compute the distance between stones two steps apart: stones[i] - stones[i-2]. Track the maximum of these distances across the array. This represents the largest jump when stones are visited in an alternating pattern, which minimizes the maximum jump for the full forward and return trip.
What is the best approach for Frog Jump II?
The best approach is a greedy skipping strategy. Instead of visiting stones strictly in order, the frog alternates stones so the forward path uses every other stone and the remaining stones are used on the return path. This reduces the largest jump and leads to a simple O(n) scan computing the maximum value of stones[i] - stones[i-2].
Is Frog Jump II asked at Google/Amazon/Meta?
Greedy array optimization problems similar to Frog Jump II frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, recognizing patterns that minimize maximum gaps using greedy strategies is a common interview theme.
What data structure is used in Frog Jump II?
The problem primarily uses a sorted array of stone positions. The optimal solution relies on greedy reasoning and simple iteration over the array rather than complex data structures.
What is the time complexity of Frog Jump II?
The optimal greedy solution runs in O(n) time and O(1) space because it scans the sorted stone array once and tracks the maximum gap between stones two indices apart. A dynamic programming formulation exists but typically requires O(n²) time and space.

Ready to solve this problem?

Practice Frog Jump II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Climbing Stairs

Next

Koko Eating Bananas