Frog Jump | Problems

A frog is crossing a river. The river is divided into units and at each unit there may or may not be a stone. Given an array stones of stone positions in sorted ascending order, the frog starts at stone 0 and its first jump must be 1 unit. If the last jump was k units, the next jump must be k-1, k, or k+1 units. The frog can only jump forward. Determine if the frog can reach the last stone.

Example 1:

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

Example 2:

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

Sample Input

—

Sample Output

—

Constraints

2 <= stones.length <= 2000
0 <= stones[i] <= 2^31 - 1
stones[0] == 0
stones is sorted in ascending order

Test Cases

Case 1

Args: [[0,1,3,5,6,8,12,17]] Expected: true

Case 2

Args: [[0,1,2,3,4,8,9,11]] Expected: false

Topics

Dynamic Programming Memoization

Approach: DP with HashMap

Map each stone position to a set of possible jump sizes that can reach it. Starting from stone 0 with jump 0, for each stone try jumps of k-1, k, and k+1. If the destination exists, add the jump size to that stone's set.

function frogJump(stones) {
  const map = new Map();
  for (const s of stones) map.set(s, new Set());
  map.get(0).add(0);
  for (const s of stones) {
    for (const k of map.get(s)) {
      for (const jump of [k-1, k, k+1]) {
        if (jump > 0 && map.has(s + jump)) map.get(s + jump).add(jump);
      }
    }
  }
  return map.get(stones[stones.length - 1]).size > 0;
}

Time Complexity: O(n²)

Space Complexity: O(n²)

Saved in this browser only. Private to you.