Medium

Minimum Sideway Jumps

LAB

A frog starts in lane 2 at position 0. Given obstacle lanes by position, return the minimum side jumps to reach the end.

EXAMPLES

Example 1

Input
{
  "obstacles": [
    0,
    1,
    2,
    3,
    0
  ]
}

Output
2

FUNCTION SHAPE

obstacles: intArray→int

SOLUTION NOTE

If next position in current lane is blocked, must jump to unblocked lane. Count jumps.

Reveal reference solution +

pythonREFERENCE

def minSideJumps(self, obstacles: List[int]) -> int:
    n = len(obstacles)

    @cache
    def dp(i, lane):
        if i == n - 1:
            return 0
        if obstacles[i + 1] != lane:
            return dp(i + 1, lane)

        # Must jump sideways
        res = float('inf')
        for new_lane in [1, 2, 3]:
            if new_lane != lane and obstacles[i] != new_lane:
                res = min(res, 1 + dp(i, new_lane))
        return res

    return dp(0, 2)  # Start in lane 2

TimeO(n)

SpaceO(n)

Open on LeetCode ↗