Code Implementation

class Solution:
    def canCross(self, stones):
        stone_set = set(stones)
        last = stones[-1]
        dp = {stone: set() for stone in stones}
        dp[0].add(0)
        for stone in stones:
            for k in dp[stone]:
                for jump in [k-1, k, k+1]:
                    if jump > 0 and (stone + jump) in stone_set:
                        dp[stone + jump].add(jump)
        return len(dp[last]) > 0
      

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> dp;
        for (int stone : stones) dp[stone] = unordered_set<int>();
        dp[0].insert(0);
        for (int stone : stones) {
            for (int k : dp[stone]) {
                for (int jump = k-1; jump <= k+1; ++jump) {
                    if (jump > 0 && dp.count(stone + jump)) {
                        dp[stone + jump].insert(jump);
                    }
                }
            }
        }
        return !dp[stones.back()].empty();
    }
};
      

class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> dp = new HashMap<>();
        for (int stone : stones) dp.put(stone, new HashSet<>());
        dp.get(0).add(0);
        for (int stone : stones) {
            for (int k : dp.get(stone)) {
                for (int jump = k - 1; jump <= k + 1; jump++) {
                    if (jump > 0 && dp.containsKey(stone + jump)) {
                        dp.get(stone + jump).add(jump);
                    }
                }
            }
        }
        return !dp.get(stones[stones.length - 1]).isEmpty();
    }
}
      

var canCross = function(stones) {
    const dp = new Map();
    for (const stone of stones) dp.set(stone, new Set());
    dp.get(0).add(0);
    for (const stone of stones) {
        for (const k of dp.get(stone)) {
            for (let jump = k - 1; jump <= k + 1; ++jump) {
                if (jump > 0 && dp.has(stone + jump)) {
                    dp.get(stone + jump).add(jump);
                }
            }
        }
    }
    return dp.get(stones[stones.length - 1]).size > 0;
};
      

Problem Description

You are given an array stones, where each element represents the position of a stone in a river in increasing order (starting at 0). A frog is initially on the first stone (position 0) and wants to reach the last stone. The frog can jump to a stone at position y from stone at position x if the jump distance is either k-1, k, or k+1, where k is the distance of the frog's previous jump. The first jump must be exactly 1 unit.

The task is to determine if the frog can reach the last stone. Each jump must land on an existing stone. The frog cannot jump backward or skip stones that are not present.

• There is only one valid path per set of jumps.
• The frog cannot reuse elements in a way that would violate the jump rules.
• The input stones is strictly increasing.

Thought Process

At first glance, the problem seems to lend itself to a brute-force recursive approach: at each stone, try all possible jump sizes (k-1, k, k+1) and see if you can eventually reach the last stone. However, this quickly becomes inefficient because the number of possible jump sequences grows exponentially as you try every combination.

To optimize, we notice that the problem has overlapping subproblems and optimal substructure, which are ideal for dynamic programming (DP). We can remember, for each stone, which jump sizes can get us there, and only proceed if that state hasn't been checked before. This avoids recalculating the same situations multiple times.

The key insight is to track, for each stone, the set of jump sizes that could have landed the frog there. Then, for each possible jump, see if it leads to another stone, and repeat. This way, we avoid redundant work and speed up the solution dramatically.

Solution Approach

• Step 1: Use a map (hash map or dictionary) to associate each stone position with a set of jump sizes that could have landed the frog there.
• Step 2: Initialize the map so that the first stone (position 0) has a jump size of 0 (since the frog starts there).
• Step 3: Iterate through each stone in order. For each jump size that could have landed on this stone, try jumps of size k-1, k, and k+1 (as long as the jump size is positive).
• Step 4: For each resulting jump, check if there is a stone at the landing position. If so, record that jump size as a way to reach that stone.
• Step 5: After processing all stones, check if the set of jump sizes for the last stone is non-empty. If so, the frog can reach the end.

The reason we use a map from stone positions to sets of jump sizes is that there may be multiple ways to reach a stone, each with a different previous jump size. By tracking all possibilities, we ensure that we consider all valid sequences.

This approach is efficient because lookups and insertions into the map and sets are O(1), and we process each stone and each possible jump only once.

Example Walkthrough

Let's walk through the example stones = [0,1,3,5,6,8,12,17]:

1. The frog starts at position 0 with a jump size of 0.
2. From position 0, the only possible jump is 1 unit (must be 1 for the first jump), landing on stone 1. So, position 1 records jump size 1.
3. At stone 1, the frog could have arrived with jump size 1. Now, try jumps of size 0, 1, and 2:
   • Jump 0: lands at position 1 (not useful, must move forward).
   • Jump 1: lands at position 2 (which doesn't exist).
   • Jump 2: lands at position 3 (exists). So, position 3 records jump size 2.
4. At stone 3, the frog could have arrived with jump size 2. Try jumps of size 1, 2, and 3:
   • Jump 1: lands at position 4 (doesn't exist).
   • Jump 2: lands at position 5 (exists). So, position 5 records jump size 2.
   • Jump 3: lands at position 6 (exists). So, position 6 records jump size 3.
5. Continue this process for each stone, updating possible jumps for each reachable stone.
6. Eventually, position 17 will have a non-empty set of jump sizes (e.g., 5), meaning the frog can reach the last stone.

This step-by-step process ensures that all valid jump sequences are considered, and the frog's progress is tracked efficiently.

Time and Space Complexity

• Brute-force approach: The naive recursive solution explores every possible sequence of jumps, which leads to exponential time complexity: O(3^n), where n is the number of stones. This is because, at each stone, there can be up to 3 choices for the next jump.
• Optimized DP approach: By using a map from stone positions to sets of jump sizes, we only process each stone and jump size combination once. The total number of states is O(n^2), since for each of the n stones, there can be up to n possible jump sizes (in the worst case).
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2), because the map can store up to n jump sizes for each stone.

The optimized approach is efficient enough for the input constraints typically given in the problem.

Summary

The "Frog Jump" problem is a classic example of dynamic programming with state tracking. By mapping each stone to the set of jump sizes that can reach it, we avoid redundant calculations and efficiently solve the problem. The key insight is to realize that the problem has overlapping subproblems and that each state (stone, last jump size) can be memoized. This leads to an elegant and efficient solution that works well within typical problem constraints.