Watch 10 video solutions for Minimum Sideway Jumps, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by Happy Coding has 2,863 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
obstacles[2] == 1, then there is an obstacle on lane 1 at point 2.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.
Example 1:
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). Note that the frog can jump over obstacles only when making side jumps (as shown at point 2).
Example 2:
Input: obstacles = [0,1,1,3,3,0] Output: 0 Explanation: There are no obstacles on lane 2. No side jumps are required.
Example 3:
Input: obstacles = [0,2,1,0,3,0] Output: 2 Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps.
Constraints:
obstacles.length == n + 11 <= n <= 5 * 1050 <= obstacles[i] <= 3obstacles[0] == obstacles[n] == 0Problem Overview: A frog starts in lane 2 on a 3‑lane road and moves forward one position at a time. Some positions contain obstacles in specific lanes. The goal is to reach the end with the minimum number of sideways lane jumps while avoiding obstacles.
Approach 1: Dynamic Programming (O(n) time, O(1) space)
This approach tracks the minimum jumps required to stay in each of the three lanes at every position. Maintain an array dp[3] where dp[i] represents the minimum side jumps needed to be in lane i. When an obstacle blocks a lane at position i, set its cost to infinity because the frog cannot stay there. Then update the other lanes by considering a side jump from the remaining valid lanes using min(dp[j] + 1). Iterate through the obstacle array once, updating the costs in place. The key insight: the frog only cares about the minimum cost to be in each lane at the current position, so you never need a full DP table. Time complexity is O(n) with constant space.
This solution relies on state transitions typical in dynamic programming. Each step decides whether to stay in the same lane or switch to another lane with a +1 cost.
Approach 2: Greedy with Backtracking (O(n) time, O(1) space)
The greedy idea: keep moving forward in the current lane until an obstacle blocks it. When that happens, perform a side jump to a lane that is not blocked at the current or next position. If multiple lanes are available, choose the one that allows the longest uninterrupted path ahead. Occasionally the initial choice might hit another obstacle soon, which triggers a backtrack and another lane switch.
This works because the frog only has three lanes and obstacles restrict movement locally. Instead of evaluating all possibilities, the algorithm greedily picks a safe lane and corrects when necessary. You scan the array of obstacles once while checking lane availability and performing minimal corrections. Time complexity remains O(n) and space complexity is O(1). The strategy blends lane selection heuristics with ideas from greedy algorithms.
Recommended for interviews: The dynamic programming solution is the one most interviewers expect. It clearly models the state of each lane and guarantees optimal transitions with minimal logic. Implementing the DP update correctly demonstrates strong understanding of state compression and optimal substructure. The greedy strategy is faster to reason about once you see the pattern, but it is harder to justify formally during interviews. Start with the DP explanation to show correctness, then mention the greedy observation as an optimization insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (State Compression) | O(n) | O(1) | Best general solution. Clear state transitions and guaranteed optimal answer. |
| Greedy with Backtracking | O(n) | O(1) | Useful when reasoning about lane availability directly and minimizing switches. |