Last updated on October 9th, 2024 at 05:53 pm

Here, We see ** Frog Jump LeetCode Solution**. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

*List of all LeetCode Solution*

*List of all LeetCode Solution*

## Topics

Dynamic Programming

## Companies

Snapchat

## Level of Question

Hard

**Frog Jump LeetCode Solution**

## Table of Contents

**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, its next jump must be either `k - 1`

, `k`

, or `k + 1`

units. The frog can only jump in the forward direction.

**Example 1:****Input:** stones = [0,1,3,5,6,8,12,17] **Output:** true **Explanation:** The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

**Example 2:****Input:** stones = [0,1,2,3,4,8,9,11] **Output:** false **Explanation:** There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

**1. Frog Jump LeetCode Solution C++**

class Solution { public: bool canCross(vector<int>& stones) { if(stones[1]-stones[0]>1) return false; return func(0, 1, stones); } bool func(int i, int jumps, vector<int> &stones){ if(i==stones.size()-1) return true; bool ans=false; for(int ind=i+1; ind<stones.size(); ind++){ if(stones[ind]-stones[i]>jumps+1) break; for(int t=-1; t<2; t++){ if(stones[ind]-stones[i]==jumps+t) ans = func(ind, jumps+t, stones) || ans; } } return ans; } };

**2. Frog Jump LeetCode Solution Java**

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

**3. Frog Jump LeetCode Solution JavaScript**

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

**4. Frog Jump LeetCode Solution Python**

class Solution(object): def canCross(self, stones): m = {} # stone positions to indices n = len(stones) dp = [[-1] * n for _ in range(n)] def solve(i, k): if i == n - 1: return True if dp[i][k] != -1: return dp[i][k] == 1 k0, kp, k1 = False, False, False if stones[i] + k in m: k0 = solve(m[stones[i] + k], k) if k > 1 and stones[i] + k - 1 in m: kp = solve(m[stones[i] + k - 1], k - 1) if stones[i] + k + 1 in m: k1 = solve(m[stones[i] + k + 1], k + 1) dp[i][k] = 1 if k0 or kp or k1 else 0 return dp[i][k] == 1 if stones[1] - stones[0] != 1: return False for i in range(n): m[stones[i]] = i return solve(1, 1)