Frog Jump

Master this topic with zero to advance depth.

Frog Jump

A frog is crossing a river. The river is divided into units and at each unit there may or may not be 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 is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

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

Visual Representation

Stones: [0, 1, 3, 5, 6, 8, 12, 17]

Jump 1: 0 -> 1 (Size 1)
Jump 2: 1 -> 3 (Size 2, allowed: 1-1, 1, 1+1)
Jump 3: 3 -> 5 (Size 2, allowed: 1, 2, 3)
...

Hard

Examples

Input: stones = [0, 1, 3, 5, 6, 8, 12, 17]
Output: true
0->1(1)->3(2)->5(2)->8(3)->12(4)->17(5)

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

Approach 1

Level I: Brute Force (Recursion)

Intuition

Try every valid jump from the current stone. For a stone at index i reached with a jump of k, the next jump can be k-1, k, or k+1.

Thought Process

Start at the first stone.
From stone at position pos, if we reached it with jump k, try positions pos + k - 1, pos + k, and pos + k + 1.
Base case: If we reach the last stone, return true.
If the target position has a stone, recurse.

⏱ O(3^N)💾 O(N)

Detailed Dry Run

stones = [0, 1, 3]

Start at 0. Only way to start is jump 1 to stone 1.
At 1, last jump was 1. Next jumps: 0 (skip), 1, 2.
Try k=2: 1 + 2 = 3. Stone 3 exists! Reached target.

java

import java.util.*;

public class Main {
    public static boolean solve(int pos, int k, Set<Integer> stoneSet, int target) {
        if (pos == target) return true;
        if (pos > target || k <= 0) return false;

        for (int nextK = k - 1; nextK <= k + 1; nextK++) {
            if (nextK > 0 && stoneSet.contains(pos + nextK)) {
                if (solve(pos + nextK, nextK, stoneSet, target)) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] stones = {0, 1, 3, 5, 6, 8, 12, 17};
        Set<Integer> stoneSet = new HashSet<>();
        for (int stone : stones) stoneSet.add(stone);
        System.out.println(solve(1, 1, stoneSet, 17)); // false
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

Cache (position, lastJump) states to avoid recomputing the same frog position visited with the same jump size.

Visual

stones=[0,1,3,5,6], target=6
solve(1, 1): -> solve(3, 2) or solve(3, 1)
solve(3,2): cached after first call!

⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

Cache key=(pos, k). solve(1,1) -> solve(3,2). solve(3,2) -> solve(5,2) or solve(5,3). Cached when revisited.

java

import java.util.*;

public class Main {
    public static boolean canCross(int[] stones) {
        Set<Integer> stoneSet = new HashSet<>();
        for (int s : stones) stoneSet.add(s);
        Map<String, Boolean> memo = new HashMap<>();
        return solve(stoneSet, stones[stones.length-1], 1, 1, memo);
    }

    static boolean solve(Set<Integer> stoneSet, int target, int pos, int k, Map<String,Boolean> memo) {
        if (pos == target) return true;
        String key = pos + "," + k;
        if (memo.containsKey(key)) return memo.get(key);
        boolean res = false;
        for (int step = k-1; step <= k+1 && !res; step++) {
            if (step > 0 && stoneSet.contains(pos + step))
                res = solve(stoneSet, target, pos+step, step, memo);
        }
        memo.put(key, res);
        return res;
    }

    public static void main(String[] args) {
        System.out.println(canCross(new int[]{0,1,3,5,6,8,12,17})); // true
    }
}

Approach 3

Level III: Dynamic Programming (Map of Sets)

Intuition

We maintain a map where the key is the stone's position and the value is a set of all possible jump sizes that could have landed the frog on that stone.

Thought Process

Initialize Map<Integer, Set<Integer>>. For each stone, create an empty set.
Add jump size 0 to the first stone (base case).
For each stone s:
- For each jump size k in map.get(s):
  - For each next jump step in {k-1, k, k+1}:
    - If step > 0 and map.containsKey(s + step):
      - Add step to the set for stone s + step.
If the set for the last stone is not empty, return true.

⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

stones = [0, 1, 3]

Stone	Jump Sizes
0	{1} (Initial jump is 1)
1	{1} (from 0+1)
3	{2} (from 1+2, k=1 -> k+1=2)
Result: True (Set for 3 is not empty)

java

import java.util.*;

public class Main {
    public static boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int stone : stones) map.put(stone, new HashSet<>());
        map.get(0).add(0);

        for (int stone : stones) {
            for (int k : map.get(stone)) {
                for (int step = k - 1; step <= k + 1; step++) {
                    if (step > 0 && map.containsKey(stone + step)) {
                        map.get(stone + step).add(step);
                    }
                }
            }
        }
        return !map.get(stones[stones.length - 1]).isEmpty();
    }

    public static void main(String[] args) {
        int[] stones = {0, 1, 3, 5, 6, 8, 12, 17};
        System.out.println(canCross(stones)); // true
    }
}

← Previous QuestionEdit Distance

Next Question →Minimum Path Sum in Grid

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.