Minimum Sideway Jumps — LeetCode 1824 Python Solution

The problem

There is a 3 lane road of length n that consists of n + 1 points labeled from 0 to n. A frog starts at point 0 in the second lane and wants to jump to point n.

Example

Input

obstacles = [0,1,2,3,0]

Output

2

Explanation

The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows).

Python solution

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        f = [1, 0, 1]
        for v in obstacles[1:]:
            for j in range(3):
                if v == j + 1:
                    f[j] = inf
                    break
            x = min(f) + 1
            for j in range(3):
                if v != j + 1:
                    f[j] = min(f[j], x)
        return min(f)

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1824. Minimum Sideway Jumps is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems