403. Frog Jump

Problem Description

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

Example 1:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

Constraints:

• 2 <= stones.length <= 2000
• 0 <= stones[i] <= 2³¹ - 1
• stones[0] == 0
• stones is sorted in a strictly increasing order.

Python Solution

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        # Create a dictionary to store possible jumps at each stone
        dp = {stone: set() for stone in stones}
        dp[0].add(0)  # Initial position with 0 jump
        
        for stone in stones:
            for jump in dp[stone]:
                # Try all possible next jumps
                for next_jump in [jump - 1, jump, jump + 1]:
                    if next_jump > 0 and stone + next_jump in dp:
                        dp[stone + next_jump].add(next_jump)
        
        # Check if last stone has any possible jumps
        return len(dp[stones[-1]]) > 0

Java Solution

class Solution {
    public boolean canCross(int[] stones) {
        Map> dp = new HashMap<>();
        
        // Initialize the dp map
        for (int stone : stones) {
            dp.put(stone, new HashSet<>());
        }
        dp.get(0).add(0);
        
        // Process each stone
        for (int stone : stones) {
            for (int jump : dp.get(stone)) {
                // Try all possible next jumps
                for (int next_jump = jump - 1; next_jump <= jump + 1; next_jump++) {
                    if (next_jump > 0 && dp.containsKey(stone + next_jump)) {
                        dp.get(stone + next_jump).add(next_jump);
                    }
                }
            }
        }
        
        // Check if last stone has any possible jumps
        return !dp.get(stones[stones.length - 1]).isEmpty();
    }
}

C++ Solution

class Solution {
public:
    bool canCross(vector& stones) {
        unordered_map> dp;
        
        // Initialize the dp map
        for (int stone : stones) {
            dp[stone] = unordered_set();
        }
        dp[0].insert(0);
        
        // Process each stone
        for (int stone : stones) {
            for (int jump : dp[stone]) {
                // Try all possible next jumps
                for (int next_jump = jump - 1; next_jump <= jump + 1; next_jump++) {
                    if (next_jump > 0 && dp.count(stone + next_jump)) {
                        dp[stone + next_jump].insert(next_jump);
                    }
                }
            }
        }
        
        // Check if last stone has any possible jumps
        return !dp[stones.back()].empty();
    }
};

JavaScript Solution

/**
 * @param {number[]} stones
 * @return {boolean}
 */
var canCross = function(stones) {
    const dp = new Map();
    
    // Initialize the dp map
    for (const stone of stones) {
        dp.set(stone, new Set());
    }
    dp.get(0).add(0);
    
    // Process each stone
    for (const stone of stones) {
        for (const jump of dp.get(stone)) {
            // Try all possible next jumps
            for (let next_jump = jump - 1; next_jump <= jump + 1; next_jump++) {
                if (next_jump > 0 && dp.has(stone + next_jump)) {
                    dp.get(stone + next_jump).add(next_jump);
                }
            }
        }
    }
    
    // Check if last stone has any possible jumps
    return dp.get(stones[stones.length - 1]).size > 0;
};

C# Solution

public class Solution {
    public bool CanCross(int[] stones) {
        var dp = new Dictionary>();
        
        // Initialize the dp dictionary
        foreach (int stone in stones) {
            dp[stone] = new HashSet();
        }
        dp[0].Add(0);
        
        // Process each stone
        foreach (int stone in stones) {
            foreach (int jump in dp[stone].ToList()) {
                // Try all possible next jumps
                for (int next_jump = jump - 1; next_jump <= jump + 1; next_jump++) {
                    if (next_jump > 0 && dp.ContainsKey(stone + next_jump)) {
                        dp[stone + next_jump].Add(next_jump);
                    }
                }
            }
        }
        
        // Check if last stone has any possible jumps
        return dp[stones[stones.Length - 1]].Count > 0;
    }
}