# Frog Jump II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/frog-jump-ii)
Canonical: https://scaleengineer.com/dsa/problems/frog-jump-ii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/frog-jump-ii/image0.png) 

**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:**

![](https://assets.glich.co/dsa/frog-jump-ii/image1.png) 

**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
## Binary Search on the Answer
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.
**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.
**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.
### Explanation
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:

```java
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.*
### 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.

## Optimal Linear Scan
A more direct and efficient approach comes from a key observation about the structure of the problem. The cost of any path is the length of its longest jump. To minimize this cost, we need to avoid long jumps.

Long jumps occur when the frog skips one or more stones. The shortest possible 'skip' jump is one that hops over a single stone, i.e., from `stones[i]` to `stones[i+2]`. The length of such a jump is `stones[i+2] - stones[i]`.

Consider any three consecutive stones `stones[i]`, `stones[i+1]`, `stones[i+2]`. For the frog to travel from the region `...stones[i]` to `stones[i+2]...` and back, the paths must somehow cover this segment. If one path takes a jump from `stones[i]` to `stones[i+2]`, the other path must handle `stones[i+1]`. This jump from `i` to `i+2` has a length of `stones[i+2] - stones[i]`. Any valid round-trip path will have a cost of at least the maximum of these `i`-to-`i+2` jumps. It turns out this is not just a lower bound, but the exact minimum cost.

Therefore, the problem reduces to a simple linear scan through the `stones` array, calculating `stones[i+2] - stones[i]` for each `i` and finding the maximum among them.
**Time:** O(N) because we perform a single pass through the `stones` array. · **Space:** O(1) as we only use a few variables to keep track of the maximum cost.
**Pros:** Extremely efficient, with optimal time and space complexity.; Very simple to implement once the core logic is understood.
**Cons:** The underlying proof that this lower bound is always achievable is non-trivial and requires careful reasoning about path construction.; It relies on a key insight that may not be immediately obvious.
### Explanation
The logic hinges on the realization that the bottleneck (the longest jump) is determined by jumps that skip exactly one stone. Let's formalize this:

*   **Lower Bound:** Let the minimum cost be `C`. Consider any `i` from `0` to `n-3`. The stones `stones[i]`, `stones[i+1]`, and `stones[i+2]` must be visited. The forward and backward paths are disjoint on intermediate stones. This means `stones[i+1]` can't be on both paths. Suppose the forward path goes from `stones[i]` to `stones[i+2]`. This jump has length `stones[i+2] - stones[i]`. Thus, the cost `C` must be at least this large. If the path doesn't jump from `i` to `i+2` directly, but via `i+1` (`i -> i+1 -> i+2`), then the other path must jump over this entire block, which would be an even longer jump. This forces the cost `C` to be at least `max(stones[i+2] - stones[i])` for all `i`.

*   **Achievability:** We can argue that a cost equal to this lower bound, let's call it `L`, is always achievable. A path can be constructed where jumps are either between adjacent stones (`i -> i+1`) or second-adjacent stones (`i -> i+2`). The length of any jump `stones[i+1] - stones[i]` is less than `stones[i+2] - stones[i]`. So, the maximum jump length will indeed be `L`.

This simplifies the algorithm to a single loop:

1.  Initialize a variable `max_cost = 0`.
2.  If `n == 2`, the only path is `0 -> 1 -> 0`, so the cost is `stones[1] - stones[0]`.
3.  Iterate from `i = 0` to `n - 3`.
4.  In each iteration, calculate the jump length `stones[i+2] - stones[i]`.
5.  Update `max_cost = max(max_cost, stones[i+2] - stones[i])`.
6.  Return `max_cost`.

This approach is extremely efficient as it only requires a single pass through the array.

```java
class Solution {
    public int maxJump(int[] stones) {
        int n = stones.length;
        if (n == 2) {
            return stones[1] - stones[0];
        }

        int maxCost = 0;
        // The first jump on the return path is from the last stone to some other stone.
        // The longest possible first jump on the return path is to the first stone, but
        // that would mean all other stones were visited on the way out. The cost would be
        // max(stones[i+1]-stones[i]) and stones[n-1]-stones[0].
        // The optimal path interleaves stones. The cost is determined by jumps over one stone.
        maxCost = stones[1] - stones[0]; // The jump 1->0 on the return path is one candidate
        for (int i = 0; i <= n - 3; i++) {
            maxCost = Math.max(maxCost, stones[i + 2] - stones[i]);
        }
        
        // The provided solution in the loop is sufficient. Let's simplify.
        // The cost is max of all (i -> i+2) jumps.
        // The jump 1->0 is not of this form, but let's check the logic.
        // Path 0->2->... and ...->3->1->0. The jumps are (i, i+2) and (j+2, j) and (1,0).
        // stones[1]-stones[0] is smaller than stones[2]-stones[0]. So we don't need to check it separately.
        
        int result = 0;
        for (int i = 2; i < n; i++) {
            result = Math.max(result, stones[i] - stones[i-2]);
        }
        return result;
    }
}
```
*The simplified code correctly captures the logic that the cost is the maximum of all `stones[i] - stones[i-2]` jumps.*
### Algorithm
1.  The core idea is to find a logical lower bound for the cost and then show that this lower bound is always achievable.
2.  Consider any three consecutive stones: `stones[i]`, `stones[i+1]`, and `stones[i+2]`.
3.  The frog's two paths (forward and backward) must somehow navigate past this triplet of stones.
4.  If one path handles all three stones in sequence (e.g., `... -> i -> i+1 -> i+2 -> ...`), the jumps are short. However, this forces the other path to make a very long jump to bypass this entire block of stones, likely leading to a high cost.
5.  To balance the jump lengths between the two paths, they must be interleaved. A common strategy is for one path to handle `stones[i]` and `stones[i+2]`, while the other handles `stones[i+1]`.
6.  If a path includes the jump `i -> i+2`, its length is `stones[i+2] - stones[i]`. This jump skips `stones[i+1]`, which must be visited by the other path.
7.  This implies that for every `i`, some jump in the total path must be at least as long as the shortest way to 'skip' a stone, which is `stones[i+2] - stones[i]`. Therefore, the final cost must be at least `max(stones[i+2] - stones[i])` over all possible `i`.
8.  It can be shown that this lower bound is always achievable. A path can be constructed where one leg of the journey primarily uses even-indexed stones and the other uses odd-indexed stones, and the maximum jump length in such a path is exactly this value.
9.  Thus, the problem simplifies to finding the maximum value of `stones[i+2] - stones[i]` for `i` from `0` to `n-3`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxJump(vector<int> &stones) {
    int ans = stones[1] - stones[0];
    for (int i = 2; i < stones.size(); ++i)
      ans = max(ans, stones[i] - stones[i - 2]);
    return ans;
  }
};

```

### Python

```python
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

```