Hard

Frog Jump

LAB

Given sorted stone positions, return true if the frog can cross by making jumps of k-1, k, or k+1 after a previous jump of k.

EXAMPLES

Example 1

Input
{
  "stones": [
    0,
    1,
    3,
    5,
    6,
    8,
    12,
    17
  ]
}

Output
true

FUNCTION SHAPE

stones: intArray→bool

SOLUTION NOTE

State is (position, last jump). Try all valid next jumps (k-1, k, k+1) that land on stones.

Reveal reference solution +

pythonREFERENCE

def canCross(self, stones: List[int]) -> bool:
    stone_set = set(stones)
    target = stones[-1]

    @cache
    def dp(pos, last_jump):
        if pos == target:
            return True
        for k in [last_jump - 1, last_jump, last_jump + 1]:
            if k > 0 and pos + k in stone_set:
                if dp(pos + k, k):
                    return True
        return False

    return dp(0, 0)

TimeO(n²)

SpaceO(n²)

Open on LeetCode ↗