Scale Engineer

Frog Jump II

Med
#2279Time: O(N * log(K)), where N is the number of stones and K is the maximum possible jump length (`stones[n-1] - stones[0]`). The `canAchieve` function takes O(N) time, and it's called O(log K) times by the binary search.Space: O(N) to store the `visited` status of each stone.
Patterns
Greedy
Algorithms
Binary Search
Data structures
Array

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

A common strategy for problems that ask to minimize a maximum value (or maximize a minimum value) is to binary search on the answer. We can binary search for the minimum possible cost. For a given cost C, we then need to determine if it's possible for the frog to make the round trip where no single jump exceeds C.

To check if a cost C is feasible, we can use a greedy approach. The frog must travel from stones[0] to stones[n-1] and then back. These two paths (forward and backward) cannot share any intermediate stones. To leave as many options as possible for the return trip, the forward trip should be constructed by making the largest possible jumps at each step, as long as the jump length does not exceed C. This way, we use the minimum number of intermediate stones for the forward journey.

After simulating the forward path, we do the same for the backward path using the remaining unvisited stones. If both the forward and backward paths can be completed, then a cost of C is achievable. The overall binary search will find the smallest C for which this is true.

Algorithm

  1. The problem asks for the minimum cost, where the cost is the maximum jump length. This structure suggests that we can binary search on the answer (the cost).
  2. If a cost C is achievable, any cost C' > C is also achievable. If C is not achievable, any C' < C is also not achievable. This monotonicity allows for binary search.
  3. We define a search range for the cost. A lower bound is 0, and an upper bound is stones[n-1] - stones[0].
  4. For each mid value in our binary search, we need a function canAchieve(cost) to check if it's possible to complete the round trip with all jumps having a length of at most cost.
  5. The canAchieve(cost) function works as follows:
    • It uses a greedy strategy. To maximize the chances of success for the return trip, the forward trip should use as few stones as possible. This is achieved by making the longest possible jumps at each step.
    • Forward Path: Start at stones[0]. From the current stone stones[i], find the furthest stone stones[j] (j > i) such that stones[j] - stones[i] <= cost. Jump to stones[j]. Repeat until stones[n-1] is reached. Keep track of all visited stones.
    • If stones[n-1] cannot be reached, cost is not achievable.
    • Backward Path: Start at stones[n-1]. From the current stone stones[i], find the furthest stone stones[j] (j < i) that was not visited on the forward path, such that stones[i] - stones[j] <= cost. Jump to stones[j]. Repeat until stones[0] is reached.
    • If stones[0] cannot be reached, cost is not achievable.
    • If both paths are successfully constructed, cost is achievable.
  6. The greedy traversals in canAchieve can be implemented efficiently in O(N) time using a two-pointer technique, rather than searching for the next stone from scratch at every step.
  7. The binary search will then narrow down the range until the minimum possible cost is found.

Walkthrough

The core of this approach is the canAchieve(cost) function. This function determines if a round trip is possible with a maximum jump length of cost.

Here's a step-by-step breakdown of canAchieve(cost):

  1. Initialize a boolean array visited of size n to keep track of the stones used in the forward path.
  2. Forward Path Simulation:
    • Start at current_stone_index = 0. Mark visited[0] = true.
    • While current_stone_index < n - 1:
      • Find the largest index next_stone_index > current_stone_index such that stones[next_stone_index] - stones[current_stone_index] <= cost.
      • To do this efficiently, we can use a search pointer that we advance from its previous position.
      • If no such stone exists (i.e., we can't even jump to the next stone), it's impossible to reach the end. Return false.
      • Move to this next_stone_index and mark it as visited.
  3. Backward Path Simulation:
    • Start at current_stone_index = n - 1.
    • While current_stone_index > 0:
      • Find the smallest index next_stone_index < current_stone_index such that stones[current_stone_index] - stones[next_stone_index] <= cost AND visited[next_stone_index] is false (or next_stone_index is 0, which is always a valid endpoint).
      • If no such stone can be found, the return trip is impossible. Return false.
      • Move to this next_stone_index.
  4. If both simulations complete successfully, it means a valid path exists for the given cost. Return true.

With this checker function, the main logic is a standard binary search:

class Solution {    public int maxJump(int[] stones) {        int low = 0, high = stones[stones.length - 1] - stones[0];        int ans = high;         while (low <= high) {            int mid = low + (high - low) / 2;            if (canAchieve(stones, mid)) {                ans = mid;                high = mid - 1;            } else {                low = mid + 1;            }        }        return ans;    }     private boolean canAchieve(int[] stones, int cost) {        int n = stones.length;        boolean[] visited = new boolean[n];                // Forward path        int currentIdx = 0;        visited[0] = true;        while (currentIdx < n - 1) {            int nextIdx = -1;            for (int i = currentIdx + 1; i < n; i++) {                if (stones[i] - stones[currentIdx] <= cost) {                    nextIdx = i;                } else {                    break;                }            }            if (nextIdx == -1) {                return false; // Cannot reach the end            }            currentIdx = nextIdx;            visited[currentIdx] = true;        }         // Backward path        currentIdx = n - 1;        while (currentIdx > 0) {            int nextIdx = -1;            for (int i = currentIdx - 1; i >= 0; i--) {                if (stones[currentIdx] - stones[i] <= cost) {                    if (!visited[i] || i == 0) {                        nextIdx = i;                    }                } else {                    break;                }            }            if (nextIdx == -1) {                return false; // Cannot reach the start            }            currentIdx = nextIdx;        }                return true;    }}

Note: The inner loops in canAchieve can be optimized to a single pass with two pointers, but this version illustrates the logic more clearly.

Complexity

Time

O(N * log(K)), where N is the number of stones and K is the maximum possible jump length (`stones[n-1] - stones[0]`). The `canAchieve` function takes O(N) time, and it's called O(log K) times by the binary search.

Space

O(N) to store the `visited` status of each stone.

Trade-offs

Pros

  • A standard and robust approach for minimax problems.

  • Relatively straightforward to reason about and implement once the binary search pattern is identified.

Cons

  • Slightly more complex to implement than the optimal linear scan solution.

  • Not the most optimal time complexity, though it is efficient enough to pass within typical time limits.

Solutions

class Solution {public  int maxJump(int[] stones) {    int ans = stones[1] - stones[0];    for (int i = 2; i < stones.length; ++i) {      ans = Math.max(ans, stones[i] - stones[i - 2]);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem