Frog Jump

HardDynamic ProgrammingDP with hashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A frog wants to cross a river by hopping across a series of stones. The stones sit at strictly increasing positions along the river, given by the sorted array stones, where stones[i] is the coordinate of the i-th stone. The frog begins on the first stone (stones[0], which is always at position 0). The frog's jumps follow one rule about momentum: if the frog's previous jump covered a distance of k units, then its next jump must cover a distance of k - 1, k, or k + 1 units. Every jump must land exactly on a stone (the frog cannot land in the water), and the frog can only move forward (the jump distance must be positive). The frog's very first jump must be exactly 1 unit, taking it from the stone at position 0 toward the stone at position 1 (if such a stone exists). Return true if the frog can reach the last stone (stones[stones.length - 1]), otherwise return false. The key challenge is that the state of the frog is not just its position but also the size of the jump it just made, since that determines which jumps are legal next. Because positions can be far apart and arbitrary, a hash structure mapping positions to stones (or memoizing (position, jumpSize) pairs) is used to drive the search efficiently.

Examples

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
One valid sequence of jump sizes is 1 (to position 1), 2 (to 3), 2 (to 5), 3 (to 8), 4 (to 12), then 5 (to 17). Every landing is on a stone, so the frog reaches the last stone.
Input: stones = [0,1,2,3,4,8,9,11]
Output: false
There is a gap of 4 units between the stone at position 4 and the stone at position 8. To clear it the frog would need a jump of size 4, but reaching position 4 forces a previous jump size too small to grow to 4 in one step, so the frog cannot cross.
Input: stones = [0,2]
Output: false
The frog's first jump must be exactly 1 unit, which would land in the water at position 1. There is no stone there, so the frog cannot make a legal first move.

Constraints

  • `2 <= stones.length <= 2000`
  • `0 <= stones[i] <= 2^31 - 1`
  • `stones[0] == 0`
  • `stones` is sorted in strictly increasing order.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.