Frog Jump - Practice Coding Problems

Frog Jump - Problem

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

Input & Output

Example 1 — Basic Case

$ Input: stones = [0,1,3,5,6,8,12,17]

› Output: true

💡 Note: Frog can jump: 0→1 (jump 1), 1→3 (jump 2), 3→5 (jump 2), 5→6 (jump 1), 6→8 (jump 2), 8→12 (jump 4), 12→17 (jump 5)

Example 2 — Impossible Case

$ Input: stones = [0,1,2,3,4,8,9,11]

› Output: false

💡 Note: Gap from stone 4 to stone 8 is too large - frog cannot jump 4 units as maximum jump from position 4 would be 3 units

Example 3 — Edge Case

$ Input: stones = [0,1,3,6,10,15]

› Output: true

💡 Note: Path exists: 0→1 (jump 1), 1→3 (jump 2), 3→6 (jump 3), 6→10 (jump 4), 10→15 (jump 5)

Constraints

2 ≤ stones.length ≤ 2000
0 ≤ stones[i] ≤ 2³¹ - 1
stones[0] == 0
stones is sorted in strictly increasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stone positions: [0,1,3,5,6,8,12,17]

Process

Find valid path with jump constraints: k-1, k, k+1

Output

Return true if frog can reach the last stone

Key Takeaway

🎯 Key Insight: Track which jump sizes can reach each stone position using dynamic programming

Asked in

G Google 45 a Amazon 32 f Facebook 28 M Microsoft 25

The key insight is to track what jump sizes can reach each stone position. The frog's jump constraint (k-1, k, or k+1) creates a dynamic programming structure. Best approach uses bottom-up DP with a 2D table. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n²)	O(n²)	Cache results of DFS to avoid recomputation
Bottom-Up Dynamic Programming	O(n²)	O(n²)	Build solution iteratively using 2D DP table
Brute Force DFS	O(3^n)	O(n)	Try all possible jump sequences recursively

Memoization (Top-Down DP) — Algorithm Steps

Use DFS with memoization cache
Cache results for each (position, jump_size) state
Return cached result if state already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute

Calculate result for each (pos, jump) state

Cache

Store result in memo table

Reuse

Return cached result for repeated states

Code -

solution.c — C

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

#define MAX_STATES 10000

typedef struct {
    int pos;
    int jumpSize;
    bool result;
    bool computed;
} MemoEntry;

MemoEntry memo[MAX_STATES];
int memoCount = 0;

bool getMemo(int pos, int jumpSize) {
    for (int i = 0; i < memoCount; i++) {
        if (memo[i].pos == pos && memo[i].jumpSize == jumpSize && memo[i].computed) {
            return memo[i].result;
        }
    }
    return false;
}

bool hasMemo(int pos, int jumpSize) {
    for (int i = 0; i < memoCount; i++) {
        if (memo[i].pos == pos && memo[i].jumpSize == jumpSize && memo[i].computed) {
            return true;
        }
    }
    return false;
}

void setMemo(int pos, int jumpSize, bool result) {
    memo[memoCount].pos = pos;
    memo[memoCount].jumpSize = jumpSize;
    memo[memoCount].result = result;
    memo[memoCount].computed = true;
    memoCount++;
}

bool dfs(int* stones, int stonesSize, int pos, int jumpSize) {
    if (pos == stonesSize - 1) {
        return true;
    }
    
    if (hasMemo(pos, jumpSize)) {
        return getMemo(pos, jumpSize);
    }
    
    bool result = false;
    int jumps[] = {jumpSize - 1, jumpSize, jumpSize + 1};
    for (int j = 0; j < 3; j++) {
        int nextJump = jumps[j];
        if (nextJump <= 0) continue;
        
        int nextPos = stones[pos] + nextJump;
        for (int i = pos + 1; i < stonesSize; i++) {
            if (stones[i] == nextPos) {
                if (dfs(stones, stonesSize, i, nextJump)) {
                    result = true;
                    break;
                }
            } else if (stones[i] > nextPos) {
                break;
            }
        }
    }
    
    setMemo(pos, jumpSize, result);
    return result;
}

bool solution(int* stones, int stonesSize) {
    if (stonesSize < 2) {
        return stonesSize == 1;
    }
    
    if (stones[1] != 1) {
        return false;
    }
    
    memoCount = 0;
    return dfs(stones, stonesSize, 1, 1);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int stones[1000];
    int stonesSize = 0;
    
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        stones[stonesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(stones, stonesSize);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each position-jump_size pair computed at most once, up to n² unique states

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization cache stores up to n² states plus recursion stack

⚠ Quadratic Space

67.0K Views

High Frequency

~25 min Avg. Time

1.8K 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

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler