Frog Jump II
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 tostones[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
5The cost of an optimal path is 5, which is the maximum jump length, and it is not possible to achieve a cost less than 5.
Example 2
Input
stones = [0,3,9]Output
9The frog can jump directly to the last stone and back to the first stone, making both jump lengths 9, which is the minimum achievable cost.
Constraints
- 2 <= stones.length <= 10^5
- 0 <= stones[i] <= 10^9
- stones[0] == 0
- stones is sorted in a strictly increasing order.
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.