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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5
6

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.

Similar Problem

Frog Jump.

Solution

Method 1 - Greedy

  1. Using every stone is always optimal, as skipping any does not reduce the path cost.
  2. Taking two consecutive stones in a path is suboptimal, since the jump from rock_i to rock_i+2 will always be larger than from rock_i to rock_i+1 due to the strictly increasing order. Thus, the minimal cost path alternates between even and odd indices, so we check both patterns and take the largest jump among them.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int maxJump(vector<int>& stones) {
        int res = stones[1]-stones[0]; // store max difference
        for(int i = 3; i < stones.size(); i+=2) res = max(res, stones[i]-stones[i-2]); // odd path
        for(int i = 2; i < stones.size(); i+=2) res = max(res, stones[i]-stones[i-2]); // even path
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func maxJump(stones []int) int {
    res := stones[1] - stones[0]
    n := len(stones)
    for i := 3; i < n; i += 2 {
        if stones[i]-stones[i-2] > res {
            res = stones[i] - stones[i-2]
        }
    }
    for i := 2; i < n; i += 2 {
        if stones[i]-stones[i-2] > res {
            res = stones[i] - stones[i-2]
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int maxJump(int[] stones) {
        int res = stones[1] - stones[0];
        for (int i = 3; i < stones.length; i += 2) {
            res = Math.max(res, stones[i] - stones[i - 2]);
        }
        for (int i = 2; i < stones.length; i += 2) {
            res = Math.max(res, stones[i] - stones[i - 2]);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maxJump(stones: IntArray): Int {
        var res = stones[1] - stones[0]
        for (i in 3 until stones.size step 2) {
            res = maxOf(res, stones[i] - stones[i - 2])
        }
        for (i in 2 until stones.size step 2) {
            res = maxOf(res, stones[i] - stones[i - 2])
        }
        return res
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def maxJump(self, stones: List[int]) -> int:
        res = stones[1] - stones[0]
        n = len(stones)
        for i in range(3, n, 2):
            res = max(res, stones[i] - stones[i - 2])
        for i in range(2, n, 2):
            res = max(res, stones[i] - stones[i - 2])
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn max_jump(stones: Vec<i32>) -> i32 {
        let mut res = stones[1] - stones[0];
        let n = stones.len();
        for i in (3..n).step_by(2) {
            res = res.max(stones[i] - stones[i - 2]);
        }
        for i in (2..n).step_by(2) {
            res = res.max(stones[i] - stones[i - 2]);
        }
        res
    }
}