Frog Jump Leetcode Solution

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Facebook Google Microsoft Oracle Salesforce Snapchat Yahoo
Array Dynamic Programming tiktokViews 246

Problem Statement

The Frog Jump LeetCode Solution – “Frog Jump” states that given the list of stones (positions) sorted in ascending order, determine if the frog can cross the river by landing on the last stone (last index of the array). Initially, the frog is on the first stone and the frog jumps 1 unit length in the first jump.

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

Example:

Input:  stones = [0,1,3,5,6,8,12,17]
Output: true

Explanation:

  • Initially, the frog jumps 1 unit to reach 2nd stone.
  • Then, the frog jumps 2 units to reach 3rd stone.
  • Then, the frog jumps 2 units to reach 4th stone.
  • Then, the frog jumps 3 units to reach the 6th stone.
  • Then, the frog jumps 4 units to reach the 7th stone.
  • Then, the frog jumps 5 units to reach the 8th stone.
Input:  stones = [0,1,2,3,4,8,9,11]
Output: false

Explanation:

  • There doesn’t exist any way to reach the last stone as the gap between the 5th and 6th stone is too large.

Approach

Idea:

  1. The main idea to solve this problem is to use dynamic programming.
  2. Consider the state as dp[i][j] = true, if there exists any path to reach ith stone provided the last jump was of j units.
  3. Let’s define base case as dp[0][0] = true.
  4. Iterate i from [1,n-1] and for each i, iterate j from [0,i-1] and let’s define difference = stones[i] – stones[j] which is the jump made by the frog to reach the ith stone from jth stone if possible.
  5. The frog can reach the ith stone only if any of the below conditions hold true:
    1. dp[j][difference] is true.
    2. dp[j][difference+1] is true.
    3. dp[j][difference-1] is true.
  6. Our answer will be true if there exists any true value in the position dp[n-1][j] where j varies from [0,n-1].

Code

Frog Jump Leetcode C++ Solution:

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        dp[0][0] = true;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                int diff = stones[i] - stones[j];
                if(diff>=n){
                    continue;
                }
                if(dp[j][diff] or (diff-1>=0 and dp[j][diff-1]) or (diff+1<n and dp[j][diff+1])){
                    dp[i][diff] = true;
                }
            }
        }
        for(int j=0;j<n;j++){
            if(dp[n-1][j]){
                return true;
            }
        }
        return false;
    }
};

Frog Jump Leetcode Java Solution:

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        boolean[][] dp = new boolean[n][n];
        dp[0][0] = true;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                int diff = stones[i] - stones[j];
                if(diff>=n){
                    continue;
                }
                if(dp[j][diff] || (diff+1<n && dp[j][diff+1]) || (diff-1>=0 && dp[j][diff-1])){
                    dp[i][diff] = true;
                }
            }
        }
        for(int j=0;j<n;j++){
            if(dp[n-1][j]){
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis for Frog Jump Leetcode Solution

Time Complexity

The time complexity of the above code is O(N^2) since we traverse the entire input array N*(N-1)/2 times.

Space Complexity

The space complexity of the above code is O(N^2) since we’re creating a boolean matrix of size N*N.

Translate »