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.
This solution uses dynamic programming (DP) to find the minimum number of side jumps the frog needs to reach the end. We initialize a DP table where dp[i][j] represents the minimum side jumps needed to reach position i on lane j. We iterate through each point, updating the DP table by considering both forward movement and sideway jumps, while skipping lanes with obstacles at the current point.
The C implementation uses a dynamic programming table to store the minimal number of jumps needed to reach each state. It processes the obstacles array and updates possible moves while respecting the presence of obstacles. We start from initialized positions on each lane and consider moving forward and sideways, ensuring obstacles are avoided.
Time Complexity: O(n), where n is the length of the obstacles array.
Space Complexity: O(1), as we are using a fixed amount of additional space for the DP table.
This approach employs a greedy strategy accompanied by backtracking to explore all possible paths minimally. Instead of maintaining a full DP table, it uses a direct comparison within available lanes to decide on the minimum jump requirements. Backtracking allows for exploration of non-optimal paths when necessary, ensuring the minimal path is found.
The C code illustrates a greedy approach by keeping the jumps minimal on-the-fly without constructing a full table of all possibilities. It adapts to obstacles dynamically by considering immediate lane options and adjusting the path accordingly.
Time Complexity: O(n), where n is the length of the `obstacles` array since we are iterating through it.
Space Complexity: O(1), only fixed auxiliary space is used.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the length of the |
| Greedy Approach with Backtracking | Time Complexity: O(n), where n is the length of the `obstacles` array since we are iterating through it. |
| 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. |
LeetCode 1824. Minimum Sideway Jumps • Happy Coding • 2,863 views views
Watch 9 more video solutions →Practice Minimum Sideway Jumps with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor