Minimum Sideway Jumps
MedPrompt
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.
- For example, if
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.
- For example, the frog can jump from lane 3 at point 3 to lane 1 at point 3.
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] == 0
Approaches
3 approaches with complexity analysis and trade-offs.
This problem exhibits optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. A top-down approach using recursion with memoization is a natural way to solve it.
We can define a function solve(point, lane) that calculates the minimum number of side jumps required to reach point on a specific lane. To avoid recomputing the same state multiple times, we use a 2D array memo to store the results of solve(point, lane).
Algorithm
- Define a recursive function, say
solve(point, lane), which returns the minimum side jumps to reachpointon the specifiedlane. - The state of our recursion is defined by the current point and the current lane.
- Create a memoization table,
memo[point][lane], to store the results of subproblems to avoid re-computation. - Base Case: If
point == 0, the frog is at the start. The cost is0for lane 2 and1for lanes 1 and 3 (one initial side jump). - Recursive Step: For
solve(point, lane): a. Check if the result is already in the memoization table. If so, return it. b. Check if there's an obstacle at(point, lane). Ifobstacles[point] == lane, it's an invalid state, so return a very large value (infinity). c. To calculate the cost to reach(point, lane), the frog must have come frompoint - 1. It could have arrived by: i. Moving straight from(point - 1, lane). The cost issolve(point - 1, lane). ii. Moving from(point - 1, other_lane)to(point, other_lane)and then making a side jump tolane. The cost issolve(point - 1, other_lane) + 1. This is only possible ifother_laneis not blocked atpoint. d. The minimum cost is the minimum of all valid possibilities frompoint - 1. e. Store the computed minimum cost inmemo[point][lane]and return it. - The final answer is the minimum of
solve(n, 1),solve(n, 2), andsolve(n, 3).
Walkthrough
The core idea is to explore all possible paths recursively. The state (point, lane) represents being at a specific location on the road. From any state at point - 1, we can transition to a state at point.
If we are calculating the minimum jumps to reach (point, lane), we consider all lanes at point - 1.
- If we come from
(point - 1, lane), we just move forward, adding no side jumps. The cost is inherited fromsolve(point - 1, lane). - If we come from another lane, say
other_lane, we must first reach(point, other_lane)and then perform a side jump. This adds 1 to the cost fromsolve(point - 1, other_lane). A key detail is that the side jump fromother_lanetolaneatpointis only possible ifother_laneitself is not blocked by an obstacle atpoint.
The final answer is the minimum cost to reach point n on any of the three lanes.
import java.util.Arrays; class Solution { private int[][] memo; private int[] obstacles; private int n; private static final int INF = 500001; // A value larger than max possible jumps public int minSideJumps(int[] obstacles) { this.n = obstacles.length - 1; this.obstacles = obstacles; this.memo = new int[n + 1][4]; for (int[] row : memo) { Arrays.fill(row, -1); } return Math.min(solve(n, 1), Math.min(solve(n, 2), solve(n, 3))); } private int solve(int point, int lane) { // Base case: at point 0 if (point == 0) { if (lane == 2) return 0; return 1; } // Memoization check if (memo[point][lane] != -1) { return memo[point][lane]; } // If there's an obstacle at the target position, it's unreachable. if (obstacles[point] == lane) { return memo[point][lane] = INF; } // Calculate cost from previous point (point - 1) int res = solve(point - 1, lane); // Consider side jumps from other lanes at the current point for (int otherLane = 1; otherLane <= 3; otherLane++) { if (otherLane == lane || obstacles[point] == otherLane) { continue; } res = Math.min(res, solve(point - 1, otherLane) + 1); } return memo[point][lane] = res; }}Complexity
Time
O(N). Each state `(point, lane)` is computed only once due to memoization. There are `N * 3` possible states. Each computation involves a constant number of operations.
Space
O(N), where N is the length of the road. This is for the memoization table `memo` of size `(N+1) x 4` and the recursion stack depth, which can go up to `N`.
Trade-offs
Pros
Relatively straightforward to implement from the problem's recursive definition.
Correctly handles all cases by exploring the entire state space.
Cons
May lead to a
StackOverflowErrorfor very largendue to deep recursion.Slightly higher constant factor overhead compared to the iterative bottom-up approach.
An iterative, or bottom-up, dynamic programming approach solves the same subproblems as the recursive solution but without using the call stack. This method is generally more efficient in practice and avoids any risk of stack overflow.
We build the solution from the start (point 0) and move forward to the end (point n). A dp table stores the minimum jumps to reach each (point, lane) combination. The value for dp[i] is computed using the already computed values for dp[i-1].
Algorithm
- Create a 2D DP table,
dp[n+1][4], wheredp[i][j]stores the minimum side jumps to reach pointion lanej. - Initialization (Base Case): At point 0, the frog starts at lane 2. So,
dp[0][2] = 0. To be on lane 1 or 3 at point 0, it must make one side jump. So,dp[0][1] = 1anddp[0][3] = 1. - Iteration: Loop from
point i = 1ton. - Transitions: For each
i, calculatedp[i][lane]for all three lanes based on the values atdp[i-1]. a. Ifobstacles[i] == lane, thendp[i][lane]is set to infinity as this position is blocked. b. Otherwise,dp[i][lane]is the minimum of: i. Coming straight from(i-1, lane):dp[i-1][lane]. ii. Coming from another lanekati-1and side-jumping ati:dp[i-1][k] + 1. This is only possible if lanekis not blocked ati(obstacles[i] != k). - Final Result: After filling the table up to
n, the minimum jumps to reach pointnismin(dp[n][1], dp[n][2], dp[n][3]).
Walkthrough
We use a dp array of size (n+1) x 4. dp[i][j] will hold the minimum side jumps to arrive at point i on lane j. We initialize the values for point 0 as the base case. Then, we iterate from i = 1 to n. In each iteration, we calculate the values for dp[i] using dp[i-1].
For each lane at point i, we check for obstacles. If a lane is clear, the frog could have arrived either by moving straight on the same lane or by side-jumping from another available lane. We take the minimum of these possibilities to find the optimal cost for dp[i][lane].
import java.util.Arrays; class Solution { public int minSideJumps(int[] obstacles) { int n = obstacles.length - 1; int[][] dp = new int[n + 1][4]; int INF = 500001; // A value larger than max possible jumps // Base case at point 0 dp[0][1] = 1; dp[0][2] = 0; dp[0][3] = 1; for (int i = 1; i <= n; i++) { int obs = obstacles[i]; for (int lane = 1; lane <= 3; lane++) { if (lane == obs) { dp[i][lane] = INF; } else { // Option 1: Come from the same lane int cost = dp[i - 1][lane]; // Option 2: Side jump from another lane for (int otherLane = 1; otherLane <= 3; otherLane++) { if (otherLane == lane || otherLane == obs) { continue; } cost = Math.min(cost, dp[i - 1][otherLane] + 1); } dp[i][lane] = cost; } } } return Math.min(dp[n][1], Math.min(dp[n][2], dp[n][3])); }}Complexity
Time
O(N). The nested loops iterate `N` times for points and a constant `3` times for lanes, resulting in linear time complexity.
Space
O(N), for the `dp` table of size `(N+1) x 4`.
Trade-offs
Pros
Avoids recursion, eliminating the risk of stack overflow.
Often slightly faster than the memoized recursion due to lower overhead.
The iterative structure can sometimes be easier to reason about and debug.
Cons
Uses O(N) space, which might be substantial for very large N, although it's within typical limits for competitive programming.
This is the most efficient approach, building upon the bottom-up DP solution. By observing that the state at point i only depends on the state at point i-1, we can optimize the space complexity. We don't need to store the entire history of DP states in a large 2D array. Instead, we only need to maintain the DP values for the previous point to calculate the values for the current point.
Algorithm
- Notice that the calculation for
dp[i]only depends on the values from the immediately preceding point,dp[i-1]. - Instead of a 2D
dptable, we can use a 1D array, saydpof size 4, to store the minimum jumps for the current point being processed. - Initialization: Initialize
dpwith the base case values for point 0:dp[1]=1,dp[2]=0,dp[3]=1. - Iteration: Loop from
point i = 1ton. a. Inside the loop, create a temporary copy of thedparray, sayprev_dp, which holds the values for pointi-1. b. Calculate the new values for thedparray (representing pointi) using the values fromprev_dp. c. The transition logic is identical to the standard DP approach. For eachlaneati, if it's not blocked, calculate its minimum cost based onprev_dp. - Final Result: After the loop finishes, the
dparray holds the values for pointn. The answer ismin(dp[1], dp[2], dp[3]).
Walkthrough
We can use a single array dp of size 4. In each step of our iteration from i = 1 to n, this array will be updated from representing the costs for point i-1 to representing the costs for point i.
A simple way to implement this is to use a prev_dp array to hold the state of i-1 while we compute the new state for i in the main dp array. A more direct implementation can be done by carefully calculating the new values. For instance, at point i, if there is an obstacle, we can first update the cost for that lane to infinity in our dp array (which currently holds i-1 values). Then, we can calculate the new costs for each lane by considering side jumps from the other two lanes.
class Solution { public int minSideJumps(int[] obstacles) { int n = obstacles.length - 1; // dp[j] = min jumps to reach point i on lane j int[] dp = new int[4]; int INF = 500001; // Base case at point 0 dp[1] = 1; dp[2] = 0; dp[3] = 1; for (int i = 1; i <= n; i++) { int obs = obstacles[i]; // First, handle the obstacle at the current point i. // If a lane has an obstacle, we can't arrive there from the previous point on the same lane. if (obs > 0) { dp[obs] = INF; } // Now, calculate the minimum jumps considering side jumps at point i. // We need to find the minimum cost to jump from another lane. // For each lane, the cost is min(cost from same lane, cost from other lanes + 1) for (int lane = 1; lane <= 3; lane++) { if (lane == obs) { continue; } int minOtherLanes = INF; for (int otherLane = 1; otherLane <= 3; otherLane++) { if (lane == otherLane || otherLane == obs) { continue; } minOtherLanes = Math.min(minOtherLanes, dp[otherLane]); } dp[lane] = Math.min(dp[lane], minOtherLanes + 1); } } return Math.min(dp[1], Math.min(dp[2], dp[3])); }}Complexity
Time
O(N). The time complexity is identical to the standard bottom-up DP approach, as we perform a constant amount of work for each of the `N` points.
Space
O(1). We only use a few arrays of constant size (4) regardless of the input size `N`.
Trade-offs
Pros
Extremely space-efficient, using only constant extra space.
Maintains the optimal O(N) time complexity.
The best solution for problems with large constraints on N.
Cons
The code can be slightly less readable as it juggles current and previous state arrays or variables.
Solutions
Solution
class Solution {public int minSideJumps(int[] obstacles) { final int inf = 1 << 30; int[] f = {1, 0, 1}; for (int i = 1; i < obstacles.length; ++i) { for (int j = 0; j < 3; ++j) { if (obstacles[i] == j + 1) { f[j] = inf; break; } } int x = Math.min(f[0], Math.min(f[1], f[2])) + 1; for (int j = 0; j < 3; ++j) { if (obstacles[i] != j + 1) { f[j] = Math.min(f[j], x); } } } return Math.min(f[0], Math.min(f[1], f[2])); }}class Solution {public: int minSideJumps(vector<int> &obstacles) { const int inf = 1 << 30; int f[3] = {1, 0, 1}; for (int i = 1; i < obstacles.size(); ++i) { for (int j = 0; j < 3; ++j) { if (obstacles[i] == j + 1) { f[j] = inf; break; } } int x = min({f[0], f[1], f[2]}) + 1; for (int j = 0; j < 3; ++j) { if (obstacles[i] != j + 1) { f[j] = min(f[j], x); } } } return min({f[0], f[1], f[2]}); }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.