Practice Minimum Sideway Jumps
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
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. However, there could be obstacles along the way. You are given an array obstacles of length n + 1 where each obstacles[i] (ranging from 0 to 3) describes an obstacle on the lane obstacles[i] at point i. If obstacles[i] == 0, there are no obstacles at point i. There will be at most one obstacle in the 3 lanes at each point. The frog can only travel from point i to point i + 1 on the same lane if there is not an obstacle on the lane at point i + 1. To avoid obstacles, the frog can also perform a side jump to jump to another lane (even if they are not adjacent) at the same point if there is no obstacle on the new lane. Return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2 at point 0. Note: There will be no obstacles on points 0 and n.
Source: Minimum Sideway Jumps on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
obstacles = [0,1,2,3,0]
2
Travel from point 0 to point 1 in lane 2. Lane 2 is blocked at point 2, so jump sideways into lane 3 at point 1, then move to point 2. Before lane 3's obstacle at point 3, jump from lane 3 directly to lane 1 at point 2. Lane 1 then reaches point 4: two sideways jumps. One jump cannot suffice: switching early to lane 1 encounters its obstacle at point 1, while switching to lane 3 encounters its obstacle at point 3. A sideways jump may cross two lanes; count lane changes, not the distance crossed.
# Example 2
obstacles = [0,1,1,3,3,0]
0
The frog starts in lane 2, and no entry in obstacles is 2. It can move forward through points 1, 2, 3, 4 and 5 without ever changing lanes, so the answer is 0. Obstacles in lanes 1 and 3 do not block lane 2. The number of obstacles is therefore not the answer: only obstacles on the chosen route matter. Since a jump count cannot be negative, this straight route is already optimal.
# Example 3
obstacles = [0,2,1,0,3,0]
2
Lane 2 is blocked at point 1, so the frog must jump sideways at point 0. Choose lane 3, then move forward to point 3. Before the obstacle in lane 3 at point 4, jump to lane 2 at point 3 and continue to point 5. This uses two sideways jumps. One jump is impossible: the initial alternative is either lane 1, which is blocked at point 2, or lane 3, which is blocked at point 4. Looking only at the next point can hide a later obstacle; keeping the best cost for each lane handles both possibilities.
Constraints
How to solve Minimum Sideway Jumps
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
At every point only three states matter, the minimum side jumps needed to stand in each lane, and a side jump at a point costs one and can reach any unblocked lane, so a three-value dynamic program swept once along the road gives the answer.
Why brute force is not enough
Exploring every sequence of lane choices is exponential, and a greedy rule such as jumping to any free lane only when blocked fails because that lane may be blocked soon after, as example 3 shows. With n up to 5 * 10^5 you need linear time.
Approach
- Start at point 0 with costs 1, 0, 1 for lanes 1, 2, 3: the frog begins in lane 2, and the other lanes are reachable right away with one side jump.
- At each next point, carry each lane's cost forward unchanged unless that lane holds the obstacle at this point, in which case set it to infinity; this models moving straight ahead.
- Then relax side jumps at the same point: each unblocked lane may take the minimum of the other two lanes' costs plus one. One pass suffices because any lane can jump directly to any other.
- The invariant after processing point i is that each lane's value is the fewest side jumps needed to stand in that lane at point i, or infinity if that lane is blocked there.
- Return the minimum of the three values at point n.
Walkthrough of Example 1
obstacles = [0,1,2,3,0] → 2
- Point 0: costs for lanes 1, 2, 3 are (1, 0, 1).
- Point 1 blocks lane 1: (infinity, 0, 1); relaxation changes nothing.
- Point 2 blocks lane 2: (infinity, infinity, 1); lane 1 can be reached from lane 3 for 1 + 1 = 2, giving (2, infinity, 1).
- Point 3 blocks lane 3: (2, infinity, infinity); lane 2 becomes 2 + 1 = 3, giving (2, 3, infinity).
- Point 4 is free: (2, 3, infinity), then lane 3 becomes 3; the minimum is 2.
Time and space
Time O(n) · Space O(1). n is the road length; each of the n + 1 points does a constant amount of work on three values.
Interview pitfalls
- Initializing all three lanes to 0 at point 0; lanes 1 and 3 must start at 1.
- Relaxing side jumps before invalidating the blocked lane, which allows jumping into or out of an obstacle.
- Writing a recursive solution; depth 5 * 10^5 overflows the call stack.
- Representing infinity with the maximum integer and then adding 1, which overflows; use n + 1 or another large sentinel.
Follow-up questions interviewers ask
- With k lanes instead of 3, how do you keep each step O(k) by using the smallest and second-smallest costs?
- How would you reconstruct the actual sequence of lane changes?
- What if a side jump to a non-adjacent lane costs the number of lanes crossed?
Further reading on the technique: Dynamic programming
Related LeetCode Problems
Practice more problems similar to Minimum Sideway Jumps.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.