403. Frog Jump

This problem asks whether a frog can reach the last stone in a river, given a list of stone positions and jump constraints. The frog starts at the first stone (position 0) and must jump to the last stone. The jump distance must be one of: k-1, k, or k+1, where k is the distance of the previous jump.

Solution Approaches and Code

Two main approaches effectively solve this problem: Memoization with Depth-First Search (DFS) and Dynamic Programming. Both have a time complexity of O(n^2), where n is the number of stones.

1. Hash Table + Memoization (DFS)

This approach uses a hash table to store the index of each stone for quick lookup. The core is a recursive DFS function dfs(i, k):

• dfs(i, k): Represents whether the frog can reach the last stone starting from stone i with the last jump being k.

• Base Case: If i is the index of the last stone, return true (frog reached the end).

• Recursive Step: Iterate through possible jump distances (k-1, k, k+1). Check if a stone exists at the calculated position (stones[i] + j). If it does, recursively call dfs for the new stone and jump distance. If the recursive call returns true, return true immediately (path found).

• Memoization: A cache (f in the code) stores the results of dfs(i,k), preventing redundant computations and significantly improving performance.

Time Complexity: O(n^2) due to the nested loop in the DFS function. Memoization reduces the worst-case time.

Space Complexity: O(n^2) for the memoization table.

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        @cache
        def dfs(i, k):
            if i == n - 1:
                return True
            for j in range(k - 1, k + 2):
                if j > 0 and stones[i] + j in pos and dfs(pos[stones[i] + j], j):
                    return True
            return False
 
        n = len(stones)
        pos = {s: i for i, s in enumerate(stones)}
        return dfs(0, 0)

(Java, C++, Go, TypeScript, and Rust implementations are similar in structure, using their respective memoization techniques and data structures.)

2. Dynamic Programming

This approach uses a 2D boolean array dp[i][k] where:

• dp[i][k] is true if the frog can reach stone i with a last jump of size k.

The algorithm iterates through the stones and updates dp based on possible previous jump sizes. If dp[n-1][k] becomes true for any k, the frog can reach the last stone.

Time Complexity: O(n^2) due to the nested loops iterating through stones and jump sizes.

Space Complexity: O(n^2) for the dp array.

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        n = len(stones)
        f = [[False] * n for _ in range(n)]
        f[0][0] = True
        for i in range(1, n):
            for j in range(i - 1, -1, -1):
                k = stones[i] - stones[j]
                if k - 1 > j:
                    break
                f[i][k] = f[j][k - 1] or f[j][k] or f[j][k + 1]
                if i == n - 1 and f[i][k]:
                    return True
        return False
 

(Similar Java, C++, Go, TypeScript, and Rust implementations exist, using their respective array and boolean handling.)

Summary

Both approaches provide correct solutions with the same time and space complexity. The choice depends on personal preference; the dynamic programming approach might be slightly easier to understand for some, while memoization can feel more intuitive to others. Both solutions are optimized to avoid redundant computations.