Frog Jump

Hard
883.

Frog Jump

Frog Jump is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google, Microsoft and Snapchat interviews.

A frog crosses a river on stones at the positions listed in stones (strictly increasing, starting at 0). It begins on the first stone and its first jump must be 1 unit.

If the last jump was k units, the next must be k - 1, k or k + 1 units, always forwards. Return whether the frog can reach the last stone.

Example 1

Input
stones = [0,1,3,5,6,8,12,17]
Output
true
Explanation
Jumps of 1, 2, 2, 3, 4 and 5 reach the end.

Example 2

Input
stones = [0,1,2,3,4,8,9,11]
Output
false
Explanation
The gap from 4 to 8 is too wide for the jump built up so far.

Example 3

Input
stones = [0,1]
Output
true

Constraints

  • 2 <= stones.length <= 1000
  • 0 <= stones[i] <= 1000000000
  • stones[0] == 0
  • stones is sorted strictly increasing.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} stones
 * @return {boolean}
 */
var canCross = function(stones) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Frog Jump — Solution in Python, Java & C++

Frog Jump solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Frog Jump is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google, Microsoft and Snapchat interviews.

Problem statement

A frog crosses a river on stones at the positions listed in stones (strictly increasing, starting at 0). It begins on the first stone and its first jump must be 1 unit.

If the last jump was k units, the next must be k - 1, k or k + 1 units, always forwards. Return whether the frog can reach the last stone.

Example 1

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: Jumps of 1, 2, 2, 3, 4 and 5 reach the end.

Example 2

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: The gap from 4 to 8 is too wide for the jump built up so far.

Example 3

Input: stones = [0,1]
Output: true

Constraints

  • 2 <= stones.length <= 1000
  • 0 <= stones[i] <= 1000000000
  • stones[0] == 0
  • stones is sorted strictly increasing.

Hints for Frog Jump

  1. Hint 1

    The state is the pair (stone, size of the jump that landed there) — position alone is not enough.

  2. Hint 2

    From a state, three jump sizes are possible, and each must land exactly on another stone.

  3. Hint 3

    Keep a set of reachable jump sizes per stone and push forwards.

How to solve Frog Jump

Forward reachability over states (stone, lastJump). From each reachable state, try the three legal jump sizes and mark the landing stone reachable with that size.

Approach

  1. Map each stone position to its index for constant-time landing checks.
  2. Seed stone 0 with jump size 0, so the only legal first move is size 1.
  3. For each stone in order, for each recorded jump size k, try k-1, k and k+1, skipping non-positive sizes.
  4. The frog can cross when the last stone has any recorded jump size.

Why it works

The next legal jumps depend only on the size of the jump just made, so (stone, lastJump) is a sufficient state. Processing stones left to right is safe because every jump moves strictly forwards, so a state is finalised before it is used. The jump size never exceeds the number of stones, which bounds the state space.

Complexity

  • Time — O(n²)
  • Space — O(n²)

Pitfalls

  • Tracking only the stone, not the jump size, loses the information the rules depend on.
  • A jump of size 0 or less is illegal and must be skipped — seeding stone 0 with 0 is what forces the first jump to be 1.
  • The landing must be exactly on a stone; there is no partial progress.

Reference solution

Python

from typing import List

def canCross(stones: List[int]) -> bool:
    n = len(stones)
    pos = {s: i for i, s in enumerate(stones)}
    dp = [set() for _ in range(n)]
    dp[0].add(0)
    for i in range(n):
        for k in list(dp[i]):
            for step in (k - 1, k, k + 1):
                if step <= 0:
                    continue
                nxt = stones[i] + step
                if nxt in pos:
                    dp[pos[nxt]].add(step)
    return len(dp[n - 1]) > 0

Java

public static boolean canCross(int[] stones) {
    int n = stones.length;
    Map<Integer, Integer> pos = new HashMap<>();
    for (int i = 0; i < n; i++) pos.put(stones[i], i);
    List<Set<Integer>> dp = new ArrayList<>();
    for (int i = 0; i < n; i++) dp.add(new HashSet<>());
    dp.get(0).add(0);
    for (int i = 0; i < n; i++) {
        for (int k : new ArrayList<>(dp.get(i))) {
            for (int step = k - 1; step <= k + 1; step++) {
                if (step <= 0) continue;
                Integer idx = pos.get(stones[i] + step);
                if (idx != null) dp.get(idx).add(step);
            }
        }
    }
    return !dp.get(n - 1).isEmpty();
}

C++

bool canCross(vector<int>& stones) {
    int n = (int) stones.size();
    unordered_map<int, int> pos;
    for (int i = 0; i < n; i++) pos[stones[i]] = i;
    vector<set<int>> dp(n);
    dp[0].insert(0);
    for (int i = 0; i < n; i++) {
        vector<int> ks(dp[i].begin(), dp[i].end());
        for (int k : ks) {
            for (int step = k - 1; step <= k + 1; step++) {
                if (step <= 0) continue;
                auto it = pos.find(stones[i] + step);
                if (it != pos.end()) dp[it->second].insert(step);
            }
        }
    }
    return !dp[n - 1].empty();
}

JavaScript

var canCross = function(stones) {
    var n = stones.length;
    var pos = {}, i;
    for (i = 0; i < n; i++) pos[stones[i]] = i;
    var dp = [];
    for (i = 0; i < n; i++) dp.push({});
    dp[0][0] = true;
    for (i = 0; i < n; i++) {
        var keys = Object.keys(dp[i]);
        for (var t = 0; t < keys.length; t++) {
            var k = Number(keys[t]);
            var steps = [k - 1, k, k + 1];
            for (var q = 0; q < 3; q++) {
                var step = steps[q];
                if (step <= 0) continue;
                var nxt = stones[i] + step;
                if (pos[nxt] !== undefined) dp[pos[nxt]][step] = true;
            }
        }
    }
    return Object.keys(dp[n - 1]).length > 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets