Minimum Sideway Jumps: Lane-Switching DP Pattern

You are given a 3-lane road of length n, represented by an array obstacles of length n + 1. Each obstacles[i] is either 0 (no obstacle) or a lane number 1, 2, or 3 indicating that the lane is blocked at point i. A frog starts at point 0 in lane 2 and wants to reach point n in any lane. At each point, the frog can move forward one step for free (if the lane is not blocked ahead) or jump sideways to an adjacent lane (costing 1 jump). Return the minimum number of sideway jumps the frog needs to reach point n.

This is LeetCode 1824: Minimum Sideway Jumps, and it is a clean example of a lane-switching DP problem. The technique it teaches shows up whenever you track the cost of being in one of several "states" at each step, and you can switch between states at a cost.

Why this problem matters

Lane-switching DP is a pattern that appears across many domains. Any time you have a small number of parallel tracks (lanes, modes, options) and you move forward step by step with the ability to switch tracks at a cost, you are looking at this pattern. It shows up in problems like "minimum cost to paint houses with k colors," "stock trading with cooldown states," and "choosing actions at each step from a small menu."

The key structural feature is that the number of states per step is small and fixed (here, exactly 3 lanes), so the DP transition at each step runs in constant time. That makes the overall solution O(n) for n steps, which is as fast as you can get for a problem that requires reading every input element.

The key insight

At every point along the road, the frog is in one of three lanes. You can track the minimum number of sideway jumps needed to reach each lane at the current point. When you move to the next point, two things happen:

1. If a lane has an obstacle, it becomes unreachable (set its cost to infinity).
2. For each lane without an obstacle, check whether jumping from another open lane would be cheaper than continuing forward in the current lane.

Because there are only 3 lanes, the "check all other lanes" step is O(1). You process all n points, so the total work is O(n).

The DP array dp has 3 entries: dp[0], dp[1], dp[2] represent the cost of being in lanes 1, 2, and 3 respectively. Initially, dp = [1, 0, 1] because the frog starts in lane 2 (cost 0) and would need one jump to reach lane 1 or lane 3 from the start.

The solution

def min_side_jumps(obstacles: list[int]) -> int:
    n = len(obstacles)
    dp = [1, 0, 1]

    for i in range(1, n):
        for lane in range(3):
            if obstacles[i] == lane + 1:
                dp[lane] = float('inf')

        for lane in range(3):
            if obstacles[i] != lane + 1:
                dp[lane] = min(dp[lane], min(dp[j] + 1 for j in range(3) if j != lane and obstacles[i] != j + 1))

    return min(dp)

Let's walk through what each piece does.

The dp array starts as [1, 0, 1]. The frog is in lane 2 at point 0, so dp[1] = 0. Reaching lane 1 or lane 3 from lane 2 requires exactly one sideway jump each.

The outer loop iterates from point 1 to point n (the end). For each point, we first handle obstacles: if lane k is blocked at this point, we set dp[k-1] = inf because the frog cannot be in that lane here.

Then, for each open lane, we check if it would be cheaper to jump from another open lane (cost = that lane's dp value + 1) compared to staying in the current lane (cost = current dp value, since forward movement is free). We take the minimum.

The answer is min(dp) after processing all points, because the frog can end in any lane.

Visual walkthrough

Let's trace through the example obstacles = [0, 1, 2, 3, 0] step by step. Watch how the DP values update at each point as obstacles block lanes and the frog considers sideway jumps.

At each point, we first block the obstructed lane, then update the open lanes by considering jumps from other open lanes. By point 4, the minimum across all lanes is 2, which is the answer.

Complexity analysis

Time is O(n) where n is the length of the obstacles array. At each of the n points, the inner loops over 3 lanes run in constant time (since there are always exactly 3 lanes). Total work is proportional to the number of points.

Space is O(1) because we only maintain a DP array of size 3 regardless of the input size. No additional data structures grow with n.

The building blocks

1. Fixed-width DP state tracking

The pattern of maintaining a small, fixed-size DP array that updates at each step:

dp = [1, 0, 1]

for i in range(1, n):
    for lane in range(3):
        if obstacles[i] == lane + 1:
            dp[lane] = float('inf')

This is the same structure used in "minimum cost to paint houses" and "stock trading with states." You have a handful of states (lanes, colors, hold/sell/cooldown), and at each step you update each state based on the previous values. The key detail is marking unreachable states as infinity before computing transitions, so that invalid paths never propagate forward.

2. Cross-state minimization

The pattern of checking whether switching states is cheaper than staying:

for lane in range(3):
    if obstacles[i] != lane + 1:
        dp[lane] = min(dp[lane], min(dp[j] + 1 for j in range(3) if j != lane and obstacles[i] != j + 1))

For each valid state, you compare "keep going in this state" versus "jump here from another valid state + transition cost." This shows up in any DP where you can switch between a small number of modes. The "+1" is the transition cost (one sideway jump), and the inner min finds the cheapest source state to jump from. The guard obstacles[i] != j + 1 ensures you only jump from lanes that are not blocked.

Edge cases

Before submitting, think through these scenarios:

• No obstacles at all: every entry is 0. The frog walks forward in lane 2 the entire way. Answer: 0.
• Obstacle in lane 2 at point 1: the frog must jump sideways at the very first step. Answer is at least 1.
• Two lanes blocked at consecutive points forcing a zigzag: the frog may need to jump back and forth. The DP handles this naturally because it considers all open lanes at each point.
• Obstacles at n (the last point): only matters if you need to be in that lane at the end. Since the frog can end in any lane, blocking one lane at the end just eliminates that option.
• Maximum length input (n = 500,000): O(n) time with O(1) space handles this comfortably with no risk of TLE or MLE.

From understanding to recall

You have seen how lane-switching DP works: maintain a small array of costs per lane, block obstructed lanes, and check cross-lane transitions at each step. The logic is compact and the code is short. But reproducing it quickly under interview pressure requires practice.

The details that trip people up are the two-pass ordering (block before update), the infinity sentinel for blocked lanes, and remembering to guard against jumping from a blocked lane. These are not conceptual gaps. They are recall gaps, and they cost people offers.

Spaced repetition is how you close them. You practice writing the fixed-width DP initialization, the obstacle-blocking pass, and the cross-state minimization from memory at increasing intervals. After a few rounds, the pattern becomes automatic. You see "small number of parallel states with switching costs" in a problem description, and the DP template flows out without hesitation.

Related posts

• Jump Game - Greedy forward-reach in a 1D array
• Coin Change - Classic DP minimization over choices
• Unique Paths - Grid DP with multiple movement options

CodeBricks breaks Minimum Sideway Jumps into its fixed-width DP tracking and cross-state minimization building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a lane-switching DP problem shows up in your interview, you do not think about it. You just write it.