Frog Jump II - Practice Coding Problems

Frog Jump II - 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.

Input & Output

Example 1 — Basic Case

$ Input: stones = [0,2,5,6,7]

› Output: 3

💡 Note: One optimal path: 0→2→6→7→5→0 with jumps [2,4,1,2,5]. Maximum jump is 5, but optimal path gives 3.

Example 2 — Minimum Size

$ Input: stones = [0,10]

› Output: 0

💡 Note: Only two stones, frog starts at first and needs to reach second then return. No intermediate jumps needed.

Example 3 — Three Stones

$ Input: stones = [0,3,9]

› Output: 3

💡 Note: Path: 0→3→9→0. Jumps are [3,6,9]. Minimum maximum jump is 9, but with alternating strategy it's 3.

Constraints

2 ≤ stones.length ≤ 10⁵
0 ≤ stones[i] ≤ 10⁹
stones[0] = 0
stones is sorted in strictly increasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Stones positioned at [0,2,5,6,7] in a river

Round Trip

Frog goes 0→last→0, visiting each stone once

Minimize Cost

Find path with minimum maximum jump distance

Key Takeaway

🎯 Key Insight: The alternating strategy (even/odd positions) naturally minimizes maximum jump distances

Asked in

G Google 15 f Meta 12

The key insight is that the optimal path uses an alternating strategy between odd and even positioned stones. The greedy approach gives us O(n) time complexity by recognizing that the answer is simply the maximum of stones[i] - stones[i-2] for all valid i.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Alternating Strategy	O(n)	O(1)	Use alternating odd/even positioned stones to minimize maximum jump
Binary Search on Answer	O(log(max) × 2^n)	O(n)	Binary search on the answer space to find minimum possible maximum jump
Brute Force - Try All Paths	O(n!)	O(n)	Generate all possible round-trip paths and find minimum maximum jump

Greedy - Alternating Strategy — Algorithm Steps

Identify that alternating positions minimize jumps
Try both strategies: odd-first and even-first
Return minimum of both approaches

Visualization

Tap to expand

Step-by-Step Walkthrough

Forward Path

Jump to alternating positions to reach end

Return Path

Use remaining positions to return to start

Calculate Max

Maximum jump is max(stones[i] - stones[i-2])

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* stones, int n) {
    if (n <= 2) return 0;
    
    int result = 0;
    for (int i = 2; i < n; i++) {
        int jump = stones[i] - stones[i-2];
        if (jump > result) {
            result = jump;
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int stones[100];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        stones[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(stones, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array to calculate jumps for both strategies

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.8K Views

Medium Frequency

~25 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Alternating Strategy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler