403. Frog Jump LeetCode Solution

Last updated: February 17, 2025

In this guide, you will get 403. Frog Jump LeetCode Solution with the best time and space complexity. The solution to Frog Jump problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Frog Jump solution in C++
Frog Jump solution in Java
Frog Jump solution in Python
Additional Resources

Problem Statement of Frog Jump

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.

Constraints:

2 <= stones.length <= 2000
0 <= stones[i] <= 231 – 1
stones[0] == 0
stones is sorted in a strictly increasing order.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

403. Frog Jump LeetCode Solution in C++

class Solution {
 public:
  bool canCross(vector<int>& stones) {
    const int n = stones.size();
    // dp[i][j] := true if a frog can make a size j jump to stones[i]
    vector<vector<bool>> dp(n, vector<bool>(n + 1));
    dp[0][0] = true;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        const int k = stones[i] - stones[j];
        if (k > n)
          continue;
        for (const int x : {k - 1, k, k + 1})
          if (0 <= x && x <= n)
            dp[i][k] = dp[i][k] || dp[j][x];
      }

    return ranges::any_of(dp.back(), [](bool val) { return val; });
  }
};
/* code provided by PROGIEZ */

403. Frog Jump LeetCode Solution in Java

class Solution {
  public boolean canCross(int[] stones) {
    final int n = stones.length;
    // dp[i][j] := 1 if a frog can make a size j jump to stones[i]
    int[][] dp = new int[n][n + 1];
    dp[0][0] = 1;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        final int k = stones[i] - stones[j];
        if (k > n)
          continue;
        for (final int x : new int[] {k - 1, k, k + 1})
          if (0 <= x && x <= n)
            dp[i][k] |= dp[j][x];
      }

    return Arrays.stream(dp[n - 1]).anyMatch(a -> a == 1);
  }
}
// code provided by PROGIEZ

403. Frog Jump LeetCode Solution in Python

class Solution:
  def canCross(self, stones: list[int]) -> bool:
    n = len(stones)
    # dp[i][j] := True if a frog can make a size j jump to stones[i]
    dp = [[False] * (n + 1) for _ in range(n)]
    dp[0][0] = True

    for i in range(1, n):
      for j in range(i):
        k = stones[i] - stones[j]
        if k > n:
          continue
        for x in (k - 1, k, k + 1):
          if 0 <= x <= n:
            dp[i][k] |= dp[j][x]

    return any(dp[-1])
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents