LeetCode 403: Frog Jump Solution in Python – A Step-by-Step Guide

What Is LeetCode 403: Frog Jump?

In LeetCode 403: Frog Jump, you’re given an array stones where each element is the position of a stone in a river, starting at 0. The frog begins on the first stone (0) and must reach the last stone. It can jump:

• k-1, k, or k+1 units from its last jump k.
• First jump from 0 must be 1 unit (to the next stone).

The catch? It can only land on stones listed in the array. You return True if the frog can reach the last stone, False if not. For example, with [0, 1, 3, 5, 6, 8, 12, 17], it can jump 1, 2, 2, 1, 2, 3, 4 to reach 17—success!

Problem Statement

• Input: An integer array stones (positions in ascending order).
• Output: A boolean—True if the frog can reach the last stone, False otherwise.
• Rules:
• Start at stones[0] = 0, first jump = 1.
• Next jump must be k-1, k, or k+1 from previous jump k.
• Must land on a stone.

Constraints

• 2 <= stones.length <= 2000.
• 0 <= stones[i] <= 2³¹ - 1.
• stones[0] = 0, strictly increasing.

Examples

• Input: stones = [0,1,3,5,6,8,12,17]
• Output: True (path: 0→1→3→5→6→8→12→17).
• Input: stones = [0,1,2,3,4,8,9,11]
• Output: False (can’t reach 11).
• Input: stones = [0,2]
• Output: False (first jump must be 1, no stone at 1).

Understanding the Problem: Hopping to the End

To solve LeetCode 403: Frog Jump in Python, we need to figure out if there’s a sequence of jumps from 0 to the last stone, following the k-1, k, k+1 rule, landing only on stones. A naive idea might be to try every possible jump path—but with up to 2000 stones and three choices per jump, that’s a huge number of tries! Instead, we’ll use:

• Best Solution (DP with Hash Map): O(n²) time, O(n²) space—tracks reachable states efficiently.
• Alternative Solution (DFS with Memoization): O(n²) time, O(n²) space—explores paths with memory.

Let’s hop into the DP with hash map solution with a clear, step-by-step explanation.

Best Solution: Dynamic Programming with Hash Map

Why This Is the Best Solution

The DP with hash map approach is the top choice because it’s efficient—O(n²) time and O(n²) space—and smartly avoids redundant work. It uses a hash map to track which stones can be reached with which jump sizes, building the solution step-by-step. It’s like giving the frog a map of every possible hop it can make, checking if the finish line is on it!

How It Works

Think of the stones as lily pads with a travel log:

• Step 1: Set Up the Log:
• Use a hash map where key is a stone position, value is a set of jump sizes (k) that can reach it.
• Step 2: Start Hopping:
• Begin at stone 0 with jump size 0 (initial state).
• First jump must be 1 to the next stone (if it exists).
• Step 3: Build the Path:
• For each stone and jump size in the log:
• Try jumps of k-1, k, k+1 to next stones.
• If a jump lands on a stone, add that stone and jump size to the log.
• Step 4: Check the Goal:
• If the last stone has any jump sizes in the log, return True.
• Step 5: Why This Works:
• The hash map ensures we only process each stone-jump pair once.
• It builds all possible paths efficiently, stopping when we know the answer.
• It’s like mapping every hop the frog can take until it either reaches the end or runs out of moves!

Step-by-Step Example

Example: stones = [0,1,3,5,6,8,12,17]

• Setup: dp = {0: {0} } (start at 0, jump 0).
• Stone 0, Jump 0:
• Try 0-1, 0, 1: only 1 valid (to 1).
• dp = {0: {0}, 1: {1} }.
• Stone 1, Jump 1:
• Try 0, 1, 2: 2 lands on 3.
• dp = {0: {0}, 1: {1}, 3: {2} }.
• Stone 3, Jump 2:
• Try 1, 2, 3: 2 lands on 5, 3 on 6.
• dp = {0: {0}, 1: {1}, 3: {2}, 5: {2}, 6: {3} }.
• Stone 5, Jump 2:
• Try 1, 2, 3: 1 on 6, 3 on 8.
• dp = {0: {0}, 1: {1}, 3: {2}, 5: {2}, 6: {3, 1}, 8: {3} }.
• Stone 6, Jump 1:
• Try 0, 1, 2: 2 on 8.
• dp = {0: {0}, 1: {1}, 3: {2}, 5: {2}, 6: {3, 1}, 8: {3, 2} }.
• Stone 6, Jump 3:
• Try 2, 3, 4: 2 on 8, 4 on 10 (skip), 6 on 12.
• dp = {0: {0}, 1: {1}, 3: {2}, 5: {2}, 6: {3, 1}, 8: {3, 2}, 12: {6} }.
• Stone 8, Jump 2:
• Try 1, 2, 3: 4 on 12.
• dp = {0: {0}, 1: {1}, 3: {2}, 5: {2}, 6: {3, 1}, 8: {3, 2}, 12: {6, 4} }.
• Stone 12, Jump 4:
• Try 3, 4, 5: 5 on 17.
• dp = {0: {0}, 1: {1}, 3: {2}, 5: {2}, 6: {3, 1}, 8: {3, 2}, 12: {6, 4}, 17: {5} }.
• Result: 17 in dp, return True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def canCross(self, stones: List[int]) -> bool:
        # Step 1: Convert stones to set for O(1) lookup
        stone_set = set(stones)

        # Step 2: DP map: stone -> set of jump sizes that reach it
        dp = {stone: set() for stone in stones}
        dp[0].add(0)  # Start at 0 with jump 0

        # Step 3: Process each stone
        for stone in stones:
            for k in dp[stone]:
                # Try jumps k-1, k, k+1
                for jump in [k-1, k, k+1]:
                    if jump > 0:  # Jump must be positive
                        next_stone = stone + jump
                        if next_stone in stone_set:
                            dp[next_stone].add(jump)

        # Step 4: Check if last stone is reachable
        return bool(dp[stones[-1]])

• Line 4: Make a set of stones for quick checks (e.g., is 3 a stone?).
• Line 7-8: Create dp map, start at 0 with jump 0 (initial state).
• Line 11-16: Loop through stones:
• Line 12: For each jump size k that reaches this stone:
• Line 13-16: Try k-1, k, k+1:
• Line 14: Only positive jumps allowed.
• Line 15-16: If jump lands on a stone, add that jump size to dp[next_stone].
• Line 19: Return True if last stone has any jump sizes (reachable).
• Time Complexity: O(n²)—n stones, up to n jump sizes per stone.
• Space Complexity: O(n²)—dp stores up to n jump sizes per n stones.

This is like a frog’s roadmap to the finish line!

Alternative Solution: DFS with Memoization

Why an Alternative Approach?

The DFS with memoization method explores all possible jump paths, remembering results to avoid repeats. It’s O(n²) time and O(n²) space—similar to DP but recursive. It’s like letting the frog try every hop, keeping a diary of what works!

How It Works

Picture it as a hop-by-hop adventure:

• Step 1: Start at 0, first jump = 1.
• Step 2: From each stone, try k-1, k, k+1 jumps.
• Step 3: Memoize (stone, k) pairs to avoid rechecking.
• Step 4: Reach last stone = True.

Step-by-Step Example

Example: stones = [0,1,3,5]

• (0, 0): Jump 1 to 1.
• (1, 1): Jump 0, 1, 2 → 2, 3 → 3.
• (3, 2): Jump 1, 2, 3 → 5.
• (5, 3): At end, True.

Code for DFS Approach

Copy codeclass Solution:
    def canCross(self, stones: List[int]) -> bool:
        stone_set = set(stones)
        memo = {}

        def dfs(stone, k):
            if stone == stones[-1]:
                return True
            if (stone, k) in memo:
                return memo[(stone, k)]

            for jump in [k-1, k, k+1]:
                if jump > 0 and stone + jump in stone_set:
                    if dfs(stone + jump, jump):
                        memo[(stone, k)] = True
                        return True
            memo[(stone, k)] = False
            return False

        return stones[1] == 1 and dfs(0, 0)

• Time Complexity: O(n²)—n states, n jumps.
• Space Complexity: O(n²)—memo storage.

It’s a hoppy exploration!

Comparing the Two Solutions

• DP with Hash Map (Best):
• Pros: O(n²), O(n²), iterative and clear.
• Cons: More setup.
• DFS with Memo (Alternative):
• Pros: O(n²), O(n²), recursive exploration.
• Cons: Stack depth.

DP wins for simplicity.

Additional Examples and Edge Cases

• [0,1]: True.
• [0,1,2]: True.
• [0,3]: False.

DP handles all.

Complexity Breakdown

• DP with Hash Map: Time O(n²), Space O(n²).
• DFS with Memo: Time O(n²), Space O(n²).

DP’s practical.

Key Takeaways

• DP Hash Map: Map the hops!
• DFS Memo: Explore with memory!
• Jumps: Rules make it fun.
• Python Tip: Sets are fast—see [Python Basics](/python/basics).

Final Thoughts: Hop to Victory

LeetCode 403: Frog Jump in Python is a river-crossing quest. DP with hash map charts the course, while DFS explores every leap. Want more DP fun? Try LeetCode 322: Coin Change or LeetCode 1143: Longest Common Subsequence. Ready to jump? Head to Solve LeetCode 403 on LeetCode and get that frog across today!