403. Frog Jump – Leetcode Solutions

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.

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        # If the second stone is not 1 unit away, the frog can't make the initial jump
        if stones[1] != 1:
            return False
        
        # Create a dictionary to map stone positions to the set of jump lengths that can reach them
        dp = {stone: set() for stone in stones}
        dp[0].add(0)  # Frog starts at the first stone with an initial jump of 0
        
        for stone in stones:
            for jump in dp[stone]:
                # Calculate the next possible jump lengths
                for next_jump in {jump - 1, jump, jump + 1}:
                    # Next jump must be positive and lead to a valid stone
                    if next_jump > 0 and stone + next_jump in dp:
                        dp[stone + next_jump].add(next_jump)
        
        # Check if the last stone has any reachable jumps
        return len(dp[stones[-1]]) > 0

class Solution {
public:
    bool canCross(vector<int>& stones) {
        // Edge case: If the second stone is not 1 unit away, the frog cannot make the first jump.
        if (stones[1] != 1) return false;

        // A map where the key is the position of a stone, and the value is a set of all possible jump distances that can reach this stone.
        unordered_map<int, unordered_set<int>> dp;

        // Initialize the map with stones.
        for (int stone : stones) {
            dp[stone] = unordered_set<int>();
        }

        // The frog starts at the first stone and the first jump is 1 unit.
        dp[stones[0]].insert(0);

        // Traverse through each stone.
        for (int stone : stones) {
            // For each possible jump that can land on the current stone.
            for (int jump : dp[stone]) {
                // Generate the next possible jumps: jump-1, jump, jump+1.
                for (int nextJump = jump - 1; nextJump <= jump + 1; ++nextJump) {
                    // Ensure the next jump is positive and leads to a valid stone.
                    if (nextJump > 0 && dp.count(stone + nextJump)) {
                        // Add the next jump to the stone it reaches.
                        dp[stone + nextJump].insert(nextJump);
                    }
                }
            }
        }

        // If the last stone has any jumps recorded, the frog can reach it.
        return !dp[stones.back()].empty();
    }
};

var canCross = function(stones) {
    // If the second stone is not exactly 1 unit away, the frog can't start its journey
    if (stones[1] !== 1) {
        return false;
    }

    // Create a map to store the positions of stones and the jumps that can reach them
    const stoneMap = new Map();
    for (const stone of stones) {
        stoneMap.set(stone, new Set());
    }

    // The frog starts at the first stone and can only jump 1 unit
    stoneMap.get(0).add(1);

    // Iterate through all stones
    for (const stone of stones) {
        // Get the set of jumps possible at this stone
        const jumps = stoneMap.get(stone);

        // Iterate over all possible jump lengths from this stone
        for (const jump of jumps) {
            // Calculate the position of the next stone the frog might reach
            const nextStone = stone + jump;

            // If the next stone exists in the map
            if (stoneMap.has(nextStone)) {
                // Add the possible jump lengths to the next stone's set
                if (jump - 1 > 0) {
                    stoneMap.get(nextStone).add(jump - 1);
                }
                stoneMap.get(nextStone).add(jump);
                stoneMap.get(nextStone).add(jump + 1);
            }
        }
    }

    // Check if there are any possible jumps to the last stone
    return stoneMap.get(stones[stones.length - 1]).size > 0;
};

class Solution {
    public boolean canCross(int[] stones) {
        // If the gap between the first two stones is greater than 1, the frog cannot jump
        if (stones[1] != 1) {
            return false;
        }

        // Create a map to associate each stone's position with the set of jump sizes
        Map<Integer, Set<Integer>> jumpsMap = new HashMap<>();

        // Initialize the map with an empty set for each stone
        for (int stone : stones) {
            jumpsMap.put(stone, new HashSet<>());
        }

        // The first stone's possible jump is 1 (as given in the problem)
        jumpsMap.get(0).add(1);

        // Iterate through each stone
        for (int i = 0; i < stones.length; i++) {
            int currentStone = stones[i];
            Set<Integer> possibleJumps = jumpsMap.get(currentStone);

            // Check all possible jump distances from this stone
            for (int jump : possibleJumps) {
                int nextPosition = currentStone + jump;

                // If the next position is the last stone, return true
                if (nextPosition == stones[stones.length - 1]) {
                    return true;
                }

                // Check if the next position exists in the stones array
                if (jumpsMap.containsKey(nextPosition)) {
                    // Add the possible next jumps (k-1, k, k+1)
                    if (jump - 1 > 0) {
                        jumpsMap.get(nextPosition).add(jump - 1);
                    }
                    jumpsMap.get(nextPosition).add(jump);
                    jumpsMap.get(nextPosition).add(jump + 1);
                }
            }
        }

        // If we have iterated through all stones and didn't reach the last one, return false
        return false;
    }
}