Frog jump

XXX. Frog Jump

Dynamic Programming

Hash Map

Problem Statement:

A frog is crossing a river by jumping on stones. Each stone is positioned at a unique point along the river. The frog starts at the first stone and must jump to the last stone.

Initially, the frog is on the first stone and can jump a distance of 1 unit. If the frog jumps k units to a stone, its next jump can only be k-1, k, or k+1 units. Determine if the frog can reach the last stone.

Algorithm:

1. Create a map where each stone position maps to a set of possible jump distances the frog can make from that stone.
2. Initialize the map for the first stone with a jump distance of 0 (starting point).
3. Iterate through all stones and for each possible jump distance from the current stone:
   • Calculate the potential next jumps: k-1, k, and k+1.
   • If the next stone exists in the map, add the corresponding jump distance to its set.
4. At the end, check if the set of the last stone is non-empty. If it is, the frog can reach the last stone; otherwise, it cannot.

Complexity:

Time Complexity: O(n²), where n is the number of stones. Each stone can contribute to updating the reachable jumps of all subsequent stones.
Space Complexity: O(n²) for the hash map storing reachable jump distances for each stone.

Java Implementation:

public boolean canCross(int[] stones) {
    // Create a map to track reachable jump distances for each stone
    Map> map = new HashMap<>();

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

    // Starting stone has an initial jump distance of 0
    map.get(0).add(0);

    // Process each stone
    for (int i = 0; i < stones.length; i++) {
        for (int k : map.get(stones[i])) {
            // Check all possible jumps: k-1, k, k+1
            for (int step = k - 1; step <= k + 1; step++) {
                if (step <= 0) continue; // Skip invalid steps

                int nextPosition = stones[i] + step;
                // If the next position exists in the map, add the step
                if (map.containsKey(nextPosition))
                    map.get(nextPosition).add(step);
            }
        }
    }

    // Check if the last stone has any reachable jumps
    return map.get(stones[stones.length - 1]).size() > 0;
}
                

Python Implementation:

def canCross(stones):
    # Create a dictionary to track reachable jump distances for each stone
    stone_map = {stone: set() for stone in stones}

    # Starting stone has an initial jump distance of 0
    stone_map[stones[0]].add(0)

    # Process each stone
    for stone in stones:
        for k in stone_map[stone]:
            # Check all possible jumps: k-1, k, k+1
            for step in [k - 1, k, k + 1]:
                if step <= 0:
                    continue  # Skip invalid steps

                next_position = stone + step
                # If the next position exists, add the step
                if next_position in stone_map:
                    stone_map[next_position].add(step)

    # Check if the last stone has any reachable jumps
    return len(stone_map[stones[-1]]) > 0
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

bool canCross(vector& stones) {
    // Create a map to track reachable jump distances for each stone
    unordered_map> stoneMap;

    // Initialize map for each stone with an empty set
    for (int stone : stones) 
        stoneMap[stone] = unordered_set();

    // Starting stone has an initial jump distance of 0
    stoneMap[stones[0]].insert(0);

    // Process each stone
    for (int stone : stones) {
        for (int k : stoneMap[stone]) {
            // Check all possible jumps: k-1, k, k+1
            for (int step = k - 1; step <= k + 1; step++) {
                if (step <= 0) continue; // Skip invalid steps

                int nextPosition = stone + step;
                // If the next position exists, add the step
                if (stoneMap.find(nextPosition) != stoneMap.end())
                    stoneMap[nextPosition].insert(step);
            }
        }
    }

    // Check if the last stone has any reachable jumps
    return !stoneMap[stones.back()].empty();
}