We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Frog Jump

Number: 403

Difficulty: Hard

Paid? No

Companies: TikTok, Google, PhonePe, Adobe, Amazon, Zomato, Snap

Problem Description

A frog is trying to cross a river by jumping on stones. The stones are placed in increasing order along the river. The frog starts at the first stone (position 0) and its first jump must be 1 unit. If the frog’s last jump was k units, then its next jump should be either k - 1, k, or k + 1 units. The frog can only jump forward and must always land on a stone. The question is: can the frog reach the last stone based on the given positions?

Key Insights

  • Use dynamic programming to track possible jump sizes that can land the frog on each stone.
  • Leverage a hash-map (or dictionary) to map each stone's position to a set of possible jump sizes that can arrive there.
  • The valid next jump sizes from a stone reached using jump k are (k-1), k, and (k+1), ensuring the jump is >0.
  • Early termination is possible as soon as the last stone is reached.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario, where n is the number of stones, because for each stone we may explore up to three possible jump sizes. Space Complexity: O(n^2) in the worst-case scenario, due to the storage of potential jump sizes for each stone in the hash-map.

Solution

The solution uses a dynamic programming approach by keeping track of all possible jump lengths that can reach every stone using a hash-map. Starting from the first stone with a known jump size (0 initially, to allow the first jump of 1 unit), for each stone, the algorithm computes the next possible stones that can be reached by jumps of size k-1, k, and k+1. If a jump results in landing on a valid stone, that jump size is stored for that stone. The process continues until the last stone is reached, in which case the function returns true. If the entire process finishes without reaching the last stone, then the answer is false.

Code Solutions

# Define the class with the canCross method.
class Solution:
    def canCross(self, stones):
        # Create a dictionary mapping each stone position to a set of jump sizes that can reach that stone.
        stone_jumps = {stone: set() for stone in stones}
        # The frog starts at the first stone with a jump of 0 (this enables the first jump of 1).
        stone_jumps[0].add(0)
        
        # Iterate over each stone.
        for stone in stones:
            # For each jump that reaches the current stone.
            for jump in stone_jumps[stone]:
                # Evaluate possible new jump sizes: k-1, k, k+1.
                for next_jump in (jump - 1, jump, jump + 1):
                    # The next jump must be positive.
                    if next_jump > 0:
                        next_stone = stone + next_jump
                        # If the calculated stone exists in the stones list.
                        if next_stone in stone_jumps:
                            stone_jumps[next_stone].add(next_jump)
                            # If the last stone is reached, return True.
                            if next_stone == stones[-1]:
                                return True
        return False

# Example usage:
# sol = Solution()
# print(sol.canCross([0,1,3,5,6,8,12,17]))  # Expected output: True
← Back to All Questions