Frog Jump

This approach uses a bottom-up dynamic programming strategy, which is often implemented iteratively. It can be thought of as a Breadth-First Search (BFS) on the state space. We build up the solution by finding all possible jump sizes that can reach each stone, starting from the first stone.

• Create a HashMap<Integer, Set<Integer>> to store, for each stone position, the set of jump sizes that can be made from it.
• Initialize the map with all stone positions and empty sets.
• Add a jump of size 1 to the set for the first stone (at position 0): map.get(0).add(1).
• Iterate through the stones array from i = 0 to n-1.
• For the current stone stones[i], get its set of possible jumps from the map.
• For each jump k in the set:
  • Calculate nextPos = stones[i] + k.
  • If nextPos is the position of the last stone, return true.
  • If there is a stone at nextPos (check using the map), update the set for nextPos by adding k-1 (if > 0), k, and k+1.
• If the loops complete without reaching the last stone, return false.

We use a HashMap where the keys are the stone positions and the values are Sets of integers. map.get(stone_pos) will store the set of jump sizes that can be made from the stone at stone_pos.

First, we initialize the map for all stone positions with empty sets. The frog starts at stones[0] (position 0) and must make a jump of size 1. So, we initialize map.get(0).add(1). We then iterate through the stones in their given order. For each stone, we look at the set of possible jump sizes k from it. For each jump size k, we calculate the next_position = stone + k. If a stone exists at next_position, we update its entry in the map. Since the last jump was k, the next jump from next_position can be k-1, k, or k+1. We add these valid (positive) jump sizes to the set for next_position.

After iterating through all stones up to the second to last, if we have managed to schedule a jump to the last stone, we return true. If the entire process completes and the last stone was never reached, it's impossible.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int stone : stones) {
            map.put(stone, new HashSet<>());
        }
        
        // First jump is 1 unit from stone 0.
        // This requires a stone at position 1.
        if (!map.containsKey(1) || stones[1] != 1) {
            return false;
        }

        map.get(0).add(1);

        for (int i = 0; i < stones.length; i++) {
            int currentStone = stones[i];
            Set<Integer> jumps = map.get(currentStone);
            for (int k : jumps) {
                int nextPos = currentStone + k;
                if (nextPos == stones[stones.length - 1]) {
                    return true;
                }
                if (map.containsKey(nextPos)) {
                    Set<Integer> nextJumps = map.get(nextPos);
                    if (k - 1 > 0) {
                        nextJumps.add(k - 1);
                    }
                    nextJumps.add(k);
                    nextJumps.add(k + 1);
                }
            }
        }

        return false;
    }
}