NUHMAN.com

📘 Problem Statement

A frog is initially at position 0 on the x-axis. It can jump to any stone within a certain distance based on the jump distance at its current position.

You are given a list of stones' positions along the x-axis, and you need to determine if the frog can reach the last stone by jumping according to these rules:

• A frog can only jump to a stone if the jump distance is positive.
• The frog can jump to a stone from another stone if the difference between their positions is the frog's current jump distance, the jump distance can be the current jump distance minus 1, the current jump distance itself, or the current jump distance plus 1.

Input:

• A list stones where each element represents the position of a stone on the x-axis.

Output:

• Return True if the frog can reach the last stone, otherwise return False.

🧠 Key Insight

This problem can be viewed as a graph traversal problem where each stone represents a node, and the frog’s valid jump distances can be seen as edges between these nodes. We need to explore all valid paths and see if the frog can reach the last stone using a depth-first search (DFS) or dynamic programming (DP).

We can also optimize this problem using memoization to avoid redundant calculations.

💡 Approach

The frog can jump from a stone to another stone if the difference between the positions is a valid jump distance. To solve this problem, we can use DFS with memoization:

• At each stone, we explore all possible valid jump distances (k-1, k, k+1).
• We recursively check if the frog can reach the last stone by applying these valid jumps.
• Use a memoization technique to store previously calculated results and avoid redundant checks.

🐍 Python Code

python

class Solution:
    def canCross(self, stones: list[int]) -> bool:
        # Step 1: Create a set of stone positions for quick lookup
        stone_positions = set(stones)
        
        # Step 2: Create a memoization dictionary to store results
        memo = {}
        
        # Step 3: DFS function to check if we can reach the last stone
        def dfs(position, jump):
            # Base case: if we reach the last stone
            if position == stones[-1]:
                return True
            # If the result is already calculated, return it
            if (position, jump) in memo:
                return memo[(position, jump)]
            
            # Explore possible next jumps: k-1, k, k+1
            for next_jump in [jump - 1, jump, jump + 1]:
                if next_jump > 0 and position + next_jump in stone_positions:
                    if dfs(position + next_jump, next_jump):
                        memo[(position, jump)] = True
                        return True
            
            # If no valid path is found, store the result as False
            memo[(position, jump)] = False
            return False
        
        # Step 4: Start DFS from the first stone with a jump of 0
        return dfs(stones[0], 0)

🔍 Step-by-Step Explanation

1. Create a Set of Stone Positions:

python

stone_positions = set(stones)

• We use a set for stone_positions to allow quick lookups to check if a position is a valid stone. This improves the performance when checking if the frog can land on a specific stone.

2. Memoization Dictionary:

python

memo = {}

• We use a memo dictionary to store previously computed results for each (position, jump) pair. This helps avoid recalculating the same scenario multiple times.

3. DFS Function:

python

def dfs(position, jump):
    if position == stones[-1]:
        return True
    if (position, jump) in memo:
        return memo[(position, jump)]
    
    for next_jump in [jump - 1, jump, jump + 1]:
        if next_jump > 0 and position + next_jump in stone_positions:
            if dfs(position + next_jump, next_jump):
                memo[(position, jump)] = True
                return True
    
    memo[(position, jump)] = False
    return False

• Base Case: If the frog reaches the last stone (stones[-1]), return True.
• Memoization: If the result for the current (position, jump) is already computed, return the stored result.
• Recursive DFS: For each valid jump (jump-1, jump, jump+1), check if the frog can reach the next stone. If so, recursively call dfs for that new position with the new jump distance.
• If a valid path is found, mark it as True in the memo and return True.

4. Start DFS from the First Stone:

python

return dfs(stones[0], 0)

• We start the DFS search from the first stone with an initial jump distance of 0.

💡 Example Walkthrough

Example 1:

python

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

Output:
True

• Step 1: Start at stone 0 with a jump of 0.
• Step 2: The frog can jump to stone 1 (from 0 to 1 with a jump of 1).
• Step 3: From stone 1, the frog can jump to stone 3 (from 1 to 3 with a jump of 2).
• Step 4: From stone 3, the frog can jump to stone 5 (from 3 to 5 with a jump of 2).
• Step 5: From stone 5, the frog can jump to stone 6 (from 5 to 6 with a jump of 1).
• Step 6: From stone 6, the frog can jump to stone 8 (from 6 to 8 with a jump of 2).
• Step 7: From stone 8, the frog can jump to stone 12 (from 8 to 12 with a jump of 4).
• Step 8: From stone 12, the frog can jump to stone 17 (from 12 to 17 with a jump of 5).
• The frog successfully reaches the last stone at position 17.

Example 2:

python

Input:
stones = [0, 1, 2, 3, 4, 8, 9, 11]

Output:
False

• Step 1: Start at stone 0 with a jump of 0.
• Step 2: The frog can jump to stone 1.
• Step 3: From stone 1, the frog can jump to stone 2, and then to stone 3.
• Step 4: However, from stone 3, no valid jumps lead to the next stones, and thus the frog cannot reach the last stone at position 11.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(N * K)Space ComplexityO(N * K)

• Time Complexity:
• N is the number of stones.
• K is the maximum jump distance, which is bounded by the number of stones (since the frog can only make jumps of size at most the number of stones).
• For each stone, we check up to three possible jumps, so the time complexity is O(N * K).
• Space Complexity:
• We store the memoization results for each (position, jump) pair, which requires O(N * K) space.

🧵 Final Thoughts

LeetCode 403 is an interesting problem that combines graph theory and dynamic programming to solve a real-world problem of finding valid paths for the frog. The approach using DFS with memoization helps optimize the solution by avoiding redundant calculations, making it efficient even for larger inputs.