Frog Jump

A frog is attempting to cross a river to reach the other side. Within the river, there are stones located at different positions given by a stones array (this array is in sorted order). Starting on the first stone (i.e. stones[0]), the frog makes a jump of size one potentially landing on the next stone. If the frog's last jump was of size x, the frog's next jump may be of size x - 1, x, or x + 1. Given these following conditions return whether or not the frog can reach the other side.

Note: The frog may only jump in the forward direction.

This question is asked by Amazon.

Example(s)

Example 1:

Input: stones = [0, 1, 10]
Output: false
Explanation:
The frog can jump from stone 0 to stone 1 (jump size 1).
From stone 1, the next jump can be size 0, 1, or 2.
  - Jump size 0: stays at position 1 (not forward)
  - Jump size 1: reaches position 2 (not a stone)
  - Jump size 2: reaches position 3 (not a stone)
The gap to stone 10 is too far (need jump size 9, but max is 2).
Cannot reach the last stone.

Example 2:

Input: stones = [0, 1, 2, 4]
Output: true
Explanation:
The frog can jump:
  - From stone 0 to stone 1 (jump size 1)
  - From stone 1 to stone 2 (jump size 1, since last was 1)
  - From stone 2 to stone 4 (jump size 2, since last was 1, can do 0, 1, or 2)
Successfully reaches the last stone.

Example 3:

Input: stones = [0, 1, 3, 5, 6, 8, 12, 17]
Output: false
Explanation:
Cannot reach the last stone with the jump constraints.

Example 4:

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

Solution

The solution uses Dynamic Programming with a hash map:

1. DP state: For each stone position, track what jump sizes can reach it
2. Base case: Stone 0 can be reached with jump size 0 (starting position)
3. Recurrence: From stone i with jump size k, can reach stones at i+k-1, i+k, i+k+1
4. Result: Check if last stone can be reached with any jump size

JavaScript Solution

JavaScript Solution - Dynamic Programming

/**
* Check if frog can cross river
* @param {number[]} stones - Array of stone positions (sorted)
* @return {boolean} - Whether frog can reach last stone
*/
function canCross(stones) {
const n = stones.length;

// Create a map: stone position -> set of jump sizes that can reach it
const dp = new Map();

// Initialize: stone 0 can be reached with jump size 0 (starting position)
dp.set(stones[0], new Set([0]));

// Create a set for fast stone position lookup
const stoneSet = new Set(stones);

// Process each stone
for (let i = 0; i < n; i++) {
  const currentPos = stones[i];
  const jumpSizes = dp.get(currentPos);
  
  if (!jumpSizes) continue; // Cannot reach this stone
  
  // For each jump size that can reach current stone
  for (const jumpSize of jumpSizes) {
    // Next jump can be jumpSize-1, jumpSize, or jumpSize+1
    for (const nextJump of [jumpSize - 1, jumpSize, jumpSize + 1]) {
      if (nextJump <= 0) continue; // Must jump forward
      
      const nextPos = currentPos + nextJump;
      
      // Check if next position is a stone
      if (stoneSet.has(nextPos)) {
        // Add this jump size to the set of jump sizes for next stone
        if (!dp.has(nextPos)) {
          dp.set(nextPos, new Set());
        }
        dp.get(nextPos).add(nextJump);
      }
    }
  }
}

// Check if last stone can be reached
const lastStone = stones[n - 1];
return dp.has(lastStone) && dp.get(lastStone).size > 0;
}

// Test cases
console.log('Example 1:', canCross([0, 1, 10])); 
// false

console.log('Example 2:', canCross([0, 1, 2, 4])); 
// true

console.log('Example 3:', canCross([0, 1, 3, 5, 6, 8, 12, 17])); 
// false

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Dynamic Programming

from typing import List

def can_cross(stones: List[int]) -> bool:
  """
  Check if frog can cross river
  
  Args:
      stones: Array of stone positions (sorted)
      
  Returns:
      bool: Whether frog can reach last stone
  """
  n = len(stones)
  
  # Create a map: stone position -> set of jump sizes that can reach it
  dp = {}
  
  # Initialize: stone 0 can be reached with jump size 0 (starting position)
  dp[stones[0]] = {0}
  
  # Create a set for fast stone position lookup
  stone_set = set(stones)
  
  # Process each stone
  for i in range(n):
      current_pos = stones[i]
      jump_sizes = dp.get(current_pos)
      
      if not jump_sizes:
          continue  # Cannot reach this stone
      
      # For each jump size that can reach current stone
      for jump_size in jump_sizes:
          # Next jump can be jumpSize-1, jumpSize, or jumpSize+1
          for next_jump in [jump_size - 1, jump_size, jump_size + 1]:
              if next_jump <= 0:
                  continue  # Must jump forward
              
              next_pos = current_pos + next_jump
              
              # Check if next position is a stone
              if next_pos in stone_set:
                  # Add this jump size to the set of jump sizes for next stone
                  if next_pos not in dp:
                      dp[next_pos] = set()
                  dp[next_pos].add(next_jump)
  
  # Check if last stone can be reached
  last_stone = stones[n - 1]
  return last_stone in dp and len(dp[last_stone]) > 0

# Test cases
print('Example 1:', can_cross([0, 1, 10]))  
# False

print('Example 2:', can_cross([0, 1, 2, 4]))  
# True

print('Example 3:', can_cross([0, 1, 3, 5, 6, 8, 12, 17]))  
# False

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Early Termination)

Here's an optimized version with early termination:

JavaScript Optimized

/**
 * Optimized with early termination
 */
function canCrossOptimized(stones) {
  const n = stones.length;
  const dp = new Map();
  dp.set(stones[0], new Set([0]));
  
  const stoneSet = new Set(stones);
  const lastStone = stones[n - 1];
  
  for (let i = 0; i < n; i++) {
    const currentPos = stones[i];
    const jumpSizes = dp.get(currentPos);
    
    if (!jumpSizes) continue;
    
    for (const jumpSize of jumpSizes) {
      for (const nextJump of [jumpSize - 1, jumpSize, jumpSize + 1]) {
        if (nextJump <= 0) continue;
        
        const nextPos = currentPos + nextJump;
        
        if (nextPos === lastStone) {
          return true; // Early termination
        }
        
        if (stoneSet.has(nextPos)) {
          if (!dp.has(nextPos)) {
            dp.set(nextPos, new Set());
          }
          dp.get(nextPos).add(nextJump);
        }
      }
    }
  }
  
  return false;
}

Python Optimized

def can_cross_optimized(stones: List[int]) -> bool:
    """
    Optimized with early termination
    """
    n = len(stones)
    dp = {stones[0]: {0}}
    stone_set = set(stones)
    last_stone = stones[n - 1]
    
    for i in range(n):
        current_pos = stones[i]
        jump_sizes = dp.get(current_pos)
        
        if not jump_sizes:
            continue
        
        for jump_size in jump_sizes:
            for next_jump in [jump_size - 1, jump_size, jump_size + 1]:
                if next_jump <= 0:
                    continue
                
                next_pos = current_pos + next_jump
                
                if next_pos == last_stone:
                    return True  # Early termination
                
                if next_pos in stone_set:
                    if next_pos not in dp:
                        dp[next_pos] = set()
                    dp[next_pos].add(next_jump)
    
    return False

Complexity

• Time Complexity: O(n²) - Where n is the number of stones. In the worst case, each stone can be reached with O(n) different jump sizes, and we process each stone.
• Space Complexity: O(n²) - In the worst case, each stone position can store O(n) different jump sizes.

Approach

The solution uses Dynamic Programming with a hash map:

1. DP state:

   • dp[position] = set of jump sizes that can reach this stone position
   • We track for each stone, what jump sizes can reach it

2. Base case:

   • Stone 0 can be reached with jump size 0 (starting position)
   • From stone 0, we can make a jump of size 1 (first jump)

3. Recurrence:

   • For each stone i with jump size k that can reach it:
     • Next jump can be k-1, k, or k+1
     • Check if positions i+(k-1), i+k, or i+(k+1) are stones
     • If yes, add that jump size to the set for that stone

4. Result:

   • Check if last stone can be reached with any jump size

Key Insights

• Dynamic Programming: Track reachable states (stone position + jump size)
• Hash map: Efficiently track which jump sizes can reach each stone
• Three choices: Next jump can be k-1, k, or k+1
• Forward only: Must jump forward (nextJump > 0)
• O(n²) time: Process each stone with potentially O(n) jump sizes

Step-by-Step Example

Let's trace through Example 2: stones = [0, 1, 2, 4]

stones = [0, 1, 2, 4]
stoneSet = {0, 1, 2, 4}

Initialize:
  dp[0] = {0}  (can reach stone 0 with jump size 0)

Process stone 0:
  currentPos = 0, jumpSizes = {0}
  For jumpSize = 0:
    Next jumps: -1, 0, 1
    -1: skip (not forward)
    0: skip (not forward)
    1: nextPos = 0 + 1 = 1
       Is 1 a stone? Yes
       dp[1] = {1}

Process stone 1:
  currentPos = 1, jumpSizes = {1}
  For jumpSize = 1:
    Next jumps: 0, 1, 2
    0: skip (not forward)
    1: nextPos = 1 + 1 = 2
       Is 2 a stone? Yes
       dp[2] = {1}
    2: nextPos = 1 + 2 = 3
       Is 3 a stone? No, skip

Process stone 2:
  currentPos = 2, jumpSizes = {1}
  For jumpSize = 1:
    Next jumps: 0, 1, 2
    0: skip (not forward)
    1: nextPos = 2 + 1 = 3
       Is 3 a stone? No, skip
    2: nextPos = 2 + 2 = 4
       Is 4 a stone? Yes
       dp[4] = {2}

Process stone 4:
  currentPos = 4, jumpSizes = {2}
  This is the last stone!

Result: dp[4] exists and has jump sizes → true

Visual Representation

Example 2: stones = [0, 1, 2, 4]

Stone positions:  0    1    2    4
                  ↑    ↑    ↑    ↑
                  Start

Jump sequence:
  Start at 0 (jump size 0)
  Jump to 1 (jump size 1)  [0 → 1]
  Jump to 2 (jump size 1)  [1 → 2, since last was 1, can do 0,1,2]
  Jump to 4 (jump size 2)  [2 → 4, since last was 1, can do 0,1,2]

DP state:
  dp[0] = {0}
  dp[1] = {1}
  dp[2] = {1}
  dp[4] = {2}

Result: true (can reach last stone)

Example 1: stones = [0, 1, 10]

Stone positions:  0    1    10
                  ↑    ↑    ↑
                  Start

Jump sequence:
  Start at 0 (jump size 0)
  Jump to 1 (jump size 1)  [0 → 1]
  From 1, next jumps can be 0, 1, or 2
    - Jump 0: stays at 1 (not forward)
    - Jump 1: reaches 2 (not a stone)
    - Jump 2: reaches 3 (not a stone)
  Cannot reach 10 (need jump size 9, but max is 2)

Result: false (cannot reach last stone)

Edge Cases

• Two stones: Check if second stone is at position 1
• Consecutive stones: All stones are consecutive, always possible
• Large gap: Gap too large to bridge with jump constraints
• First stone not at 0: Problem states stones[0] is starting point
• Single stone: Return true (already at destination)

Important Notes

• First jump: Must be size 1 (from problem statement)
• Jump constraints: Next jump can only be k-1, k, or k+1
• Forward only: Cannot jump backward or stay in place
• O(n²) time: Must process all stones and jump sizes
• Hash map: Efficiently track reachable states

Why Dynamic Programming Works

Optimal Substructure:

• To reach stone i with jump size k, we need to:
  • Reach some previous stone j with jump size k-1, k, or k+1
  • Then jump from j to i
• The optimal solution uses optimal solutions to subproblems

Overlapping Subproblems:

• Multiple paths may lead to the same state (same stone with same jump size)
• DP stores and reuses these results

Related Problems

• Jump Game: Similar jumping problem
• Jump Game II: Minimum jumps needed
• Unique Paths: Different DP problem
• Climbing Stairs: Simpler jumping problem

Takeaways

• Dynamic Programming solves this efficiently
• Hash map tracks reachable states (position + jump size)
• Three choices per jump: k-1, k, or k+1
• O(n²) time to process all stones
• Classic DP problem with state tracking