Frog Jump Hard 0 attempts
LeetCode ↗

Frog Jump

Hard Dynamic ProgrammingMemoization LeetCode

A frog needs to cross a river that's divided into evenly spaced units, some of which have stones. You're given the positions of the stones as a sorted array stones, with the frog beginning on the stone at position 0 and required to make its very first jump exactly 1 unit forward. After a jump of k units, its next jump must measure k-1, k, or k+1 units, and it can only ever jump forward. Determine whether the frog is able to reach the final stone.

Input Format
Implement frogJump(stones). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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
Constraints
  • 2 <= stones.length <= 2000
  • 0 <= stones[i] <= 2^31 - 1
  • stones[0] == 0
  • stones is sorted in ascending order
Test Cases (2)
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 ProgrammingMemoization

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.

javascript
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.

JavaScript