LeetCode 403: Frog Jump Solution

Master LeetCode problem 403 (Frog Jump), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

403. Frog Jump

Hard

Array Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We can maintain a set for each stone position, where the set contains the possible jump distances that can reach that stone. We iterate through each stone and for each stone, we iterate through all previous stones to see if we can reach the current stone using a valid jump distance. If we can reach the last stone, then the frog can cross the river.

The time complexity of this solution is O(n^2), where n is the number of stones. The space complexity is also O(n^2) because of the sets we maintain for each stone.

Solution Code

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        if (stones[1] != 1) {
            return false;
        }

        Set<Integer>[] dp = new HashSet[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashSet<>();
        }

        dp[0].add(0);
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                int dist = stones[i] - stones[j];
                if (dp[j].contains(dist) || dp[j].contains(dist - 1) || dp[j].contains(dist + 1)) {
                    dp[i].add(dist);
                }
            }
        }

        return !dp[n - 1].isEmpty();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 403 (Frog Jump)?

This page provides optimized solutions for LeetCode problem 403 (Frog Jump) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 403 (Frog Jump)?

The time complexity for LeetCode 403 (Frog Jump) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 403 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 403 in Java, C++, or Python.

Back to LeetCode Solutions