Frog Position After T Seconds - Leetcode Solution

Problem Statement:

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Constraints:

1. 2 ≤ stones.length ≤ 2000
2. 0 ≤ stones[i] ≤ 2^31 - 1
3. stones[0] == 0

Solution:

Approach 1: Recursion

In the brute force approach, we can recursively check all possible jumps from the current stone and see if any of them leads to the last stone. If we reach the last stone, we return True. If we reach a position where the frog has no options to jump or falls into the water, we return False. This approach would have an exponential time complexity, i.e., O(3^n), which is not practical.

Approach 2: Recursion with Memoization

As we can observe in the above approach, we end up calculating the same subproblems multiple times. We can use memoization to store the result of each subproblem and reuse it when that subproblem is encountered again, reducing the time complexity significantly.

We create a memo dictionary to store the result of each subproblem, where each key is a tuple of the current stone position and the last jump made from that position. We return the memo value if it exists, and otherwise, we compute it recursively and store it in the memo dictionary.

We also optimize the recursion such that if the frog jumps out of the bounds of the stones or lands on a stone that does not exist, we directly return False. This approach has a time complexity of O(n^2) and a space complexity of O(n^2) due to the memo dictionary.

Approach 3: Dynamic Programming

We can use a dynamic programming approach to solve this problem. We define a 2D array dp, where dp[i][k] represents whether the frog can reach the ith stone with a last jump of k. Initially, we set all the values of dp as False, except for dp[0][0], which is True, as the frog starts on the first stone with a last jump of 0.

We iterate through the stones and for each stone, we iterate through the previous stones and the three possible last jumps from that stone. If the last jump is within the bounds of the previous stone and dp[j][last_jump] is True, we set dp[i][curr_jump] as True, where curr_jump is the jump from the previous stone to the current stone.

During the iteration, we also check if the frog has landed on the last stone, i.e., dp[-1][j]=True, where j is the last jump from the second last stone. If any of the dp[-1] values are True, we return True; otherwise, we return False.

This approach has a time complexity of O(n^2) and a space complexity of O(n^2) for the dp array.

Code:

Approach 2: Recursion with Memoization

class Solution: def canCross(self, stones: List[int]) -> bool: memo = {} n = len(stones)

    def helper(i, last_jump):
        if i == n-1:
            return True
        if (i, last_jump) in memo:
            return memo[(i, last_jump)]
        for next_jump in [last_jump-1, last_jump, last_jump+1]:
            if next_jump > 0:
                next_stone = stones[i] + next_jump
                j = i + 1
                while j < n and stones[j] < next_stone:
                    j += 1
                if j < n and stones[j] == next_stone:
                    if helper(j, next_jump):
                        memo[(i, last_jump)] = True
                        return True
        memo[(i, last_jump)] = False
        return False
    
    return helper(0, 0)

Approach 3: Dynamic Programming

class Solution: def canCross(self, stones: List[int]) -> bool: n = len(stones) dp = [[False]*n for _ in range(n)] dp[0][0] = True

    for i in range(1, n):
        for j in range(i-1, -1, -1):
            curr_jump = stones[i] - stones[j]
            if curr_jump <= j+1:
                dp[i][curr_jump] = dp[j][curr_jump-1] or dp[j][curr_jump] or dp[j][curr_jump+1]
            if i == n-1 and dp[i][j]:
                return True
    return False

1