Minimum Sideway Jumps solution and explanation
Google
9 more videos on this problem
LeetCode 1824. Minimum Sideway JumpsHappy Coding · 20:48 · 2K views
1824. Minimum Sideway Jumps (Leetcode Medium)Programming Live with Larry · 35:09 · 987 views
【每日一题】1824. Minimum Sideway Jumps, 4/13/2021Huifeng Guan · 12:11 · 540 views
LeetCode 1824. Minimum Sideway Jumps | Weekly Contest 236宰相小甘罗 · 3:42 · 523 views
1824. Minimum Sideway Jumps - Daily Leetcode (Day 9)yeetcode · 28:55 · 437 views
Leetcode 1824. Minimum Sideway JumpsElite Code · 25:47 · 392 views
LeetCode 1824. Minimum Sideway Jumps 中文 | Weekly Contest 236宰相小甘罗 · 3:57 · 175 views
MINIMUM SIDEWAY JUMPS || 2d DPLet's start from 0(Adithya_Nanuvala) · 12:26 · 135 views
1824. Minimum Sideway JumpsAlgorithms for Big Bucks · 6:37 · 89 views
Lecture 117: Minimum Sideways Jump LeetCode || 2D-DP || DP SeriesCodeHelp - by Babbar · 50:31 · 55K views
The problem
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
Approach overview
Problem 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 1: Dynamic Programming Approach
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.
class Solution:
def minSideJumps(self, obstacles):
dp = [1, 0, 1] # Initial state for lanes
for i in range(1, len(obstacles)):
next_dp = [float('inf')] * 3
for j in range(3):
if obstacles[i] != j + 1:
next_dp[j] = dp[j]
for j in range(3):
if obstacles[i] != j + 1:
for k in range(3):
if j != k and obstacles[i] != k + 1:
next_dp[j] = min(next_dp[j], dp[k] + 1)
dp = next_dp
return min(dp)
# Example usage
sol = Solution()
print(sol.minSideJumps([0, 1, 2, 3, 0])) # Output: 2import java.util.Arrays;
public class Solution {
public int minSideJumps(int[] obstacles) {
int[] dp = {1, 0, 1}; // Initial state for lanes
for (int i = 1; i < obstacles.length; i++) {
int[] nextDp = {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
for (int j = 0; j < 3; j++) {
if (obstacles[i] != j + 1) {
nextDp[j] = dp[j];
}
}
for (int j = 0; j < 3; j++) {
if (obstacles[i] != j + 1) {
for (int k = 0; k < 3; k++) {
if (j != k && obstacles[i] != k + 1) {
nextDp[j] = Math.min(nextDp[j], dp[k] + 1);
}
}
}
}
dp = nextDp;
}
return Arrays.stream(dp).min().getAsInt();
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] obstacles = {0, 1, 2, 3, 0};
System.out.println(sol.minSideJumps(obstacles)); // Output: 2
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minSideJumps(vector<int>& obstacles) {
vector<int> dp = {1, 0, 1}; // Initial state: [1,0,1]
for (size_t i = 1; i < obstacles.size(); ++i) {
vector<int> nextDp(3, INT_MAX);
for (int j = 0; j < 3; ++j) {
if (obstacles[i] != j + 1) {
nextDp[j] = dp[j];
}
}
for (int j = 0; j < 3; ++j) {
if (obstacles[i] != j + 1) {
for (int k = 0; k < 3; ++k) {
if (j != k && obstacles[i] != k + 1) {
nextDp[j] = min(nextDp[j], dp[k] + 1);
}
}
}
}
dp = nextDp;
}
return *min_element(dp.begin(), dp.end());
}
};
int main() {
Solution solution;
vector<int> obstacles = {0, 1, 2, 3, 0};
cout << solution.minSideJumps(obstacles) << endl; // Output: 2
return 0;
}var minSideJumps = function(obstacles) {
let dp = [1, 0, 1];
for (let i = 1; i < obstacles.length; i++) {
let nextDp = [Infinity, Infinity, Infinity];
for (let j = 0; j < 3; j++) {
if (obstacles[i] !== j + 1) {
nextDp[j] = dp[j];
}
}
for (let j = 0; j < 3; j++) {
if (obstacles[i] !== j + 1) {
for (let k = 0; k < 3; k++) {
if (j !== k && obstacles[i] !== k + 1) {
nextDp[j] = Math.min(nextDp[j], dp[k] + 1);
}
}
}
}
dp = nextDp.slice();
}
return Math.min(...dp);
};
// Example usage
console.log(minSideJumps([0, 1, 2, 3, 0])); // Output: 2#include <stdio.h>
#include <limits.h>
int minSideJumps(int* obstacles, int obstaclesSize) {
int dp[3];
dp[0] = 1;
dp[1] = 0;
dp[2] = 1;
for (int i = 1; i < obstaclesSize; i++) {
int nextDp[3] = {INT_MAX, INT_MAX, INT_MAX};
for (int j = 0; j < 3; j++) {
if (obstacles[i] != j + 1)
nextDp[j] = dp[j];
}
for (int j = 0; j < 3; j++) {
if (obstacles[i] != j + 1) {
for (int k = 0; k < 3; k++) {
if (j != k && obstacles[i] != k + 1) {
nextDp[j] = fmin(nextDp[j], dp[k] + 1);
}
}
}
}
memcpy(dp, nextDp, sizeof(dp));
}
return fmin(dp[0], fmin(dp[1], dp[2]));
}
int main() {
int obstacles[] = {0, 1, 2, 3, 0};
int result = minSideJumps(obstacles, 5);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int MinSideJumps(int[] obstacles) {
int[] dp = {1, 0, 1}; // Initial state for the lanes
for (int i = 1; i < obstacles.Length; i++) {
int[] nextDp = {int.MaxValue, int.MaxValue, int.MaxValue};
for (int j = 0; j < 3; j++) {
if (obstacles[i] != j + 1) {
nextDp[j] = dp[j];
}
}
for (int j = 0; j < 3; j++) {
if (obstacles[i] != j + 1) {
for (int k = 0; k < 3; k++) {
if (j != k && obstacles[i] != k + 1) {
nextDp[j] = Math.Min(nextDp[j], dp[k] + 1);
}
}
}
}
dp = nextDp;
}
return Math.Min(dp[0], Math.Min(dp[1], dp[2]));
}
public static void Main() {
Solution solution = new Solution();
int[] obstacles = {0, 1, 2, 3, 0};
Console.WriteLine(solution.MinSideJumps(obstacles)); // Output: 2
}
}The Python implementation closely resembles the approach in the other languages. It involves setting up a dynamic programming table that tracks minimal side jumps, updating possibilities according to the obstacles array, and maintaining efficient state transitions.
Time Complexity: O(n), where n is the length of the obstacles array.
Space Complexity: O(1), as we use a constant amount of space for storage regardless of input size.
Approach 2: Greedy Approach with Backtracking
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.
class Solution:
def minSideJumps(self, obstacles):
current_lane = 1
side_jumps = 0
for i in range(1, len(obstacles)):
if obstacles[i] == current_lane + 1:
min_jump = float('inf')
for lane in range(3):
if lane != current_lane and obstacles[i] != lane + 1:
if min_jump > side_jumps:
min_jump = side_jumps + 1
side_jumps = min_jump
current_lane = (current_lane + 1) % 3
return side_jumps
# Example usage
sol = Solution()
print(sol.minSideJumps([0, 1, 2, 3, 0]))public class Solution {
public int minSideJumps(int[] obstacles) {
int currentLane = 1;
int sideJumps = 0;
for (int i = 1; i < obstacles.length; i++) {
if (obstacles[i] == currentLane + 1) {
int minJump = Integer.MAX_VALUE;
for (int lane = 0; lane < 3; lane++) {
if (lane != currentLane && obstacles[i] != lane + 1) {
if (minJump > sideJumps) {
minJump = sideJumps + 1;
}
}
}
sideJumps = minJump;
currentLane = (currentLane + 1) % 3;
}
}
return sideJumps;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] obstacles = {0, 1, 2, 3, 0};
System.out.println(sol.minSideJumps(obstacles));
}
}#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
int minSideJumps(vector<int>& obstacles) {
int currentLane = 1;
int sideJumps = 0;
for (int i = 1; i < obstacles.size(); ++i) {
if (obstacles[i] == currentLane + 1) {
int minJump = INT_MAX;
for (int lane = 0; lane < 3; ++lane) {
if (lane != currentLane && obstacles[i] != lane + 1) {
if (minJump > sideJumps) {
minJump = sideJumps + 1;
}
}
}
sideJumps = minJump;
currentLane = (currentLane + 1) % 3;
}
}
return sideJumps;
}
};
int main() {
Solution solution;
vector<int> obstacles = {0, 1, 2, 3, 0};
cout << solution.minSideJumps(obstacles) << endl;
return 0;
}var minSideJumps = function(obstacles) {
let currentLane = 1;
let sideJumps = 0;
for (let i = 1; i < obstacles.length; i++) {
if (obstacles[i] === currentLane + 1) {
let minJump = Infinity;
for (let lane = 0; lane < 3; lane++) {
if (lane !== currentLane && obstacles[i] !== lane + 1) {
if (minJump > sideJumps) {
minJump = sideJumps + 1;
}
}
}
sideJumps = minJump;
currentLane = (currentLane + 1) % 3;
}
}
return sideJumps;
};
// Example
console.log(minSideJumps([0, 1, 2, 3, 0]));#include <stdio.h>
#include <limits.h>
int minSideJumps(int* obstacles, int obstaclesSize) {
int currentLane = 1; // Start at lane 2 (index 1)
int sideJumps = 0;
for (int i = 1; i < obstaclesSize; ++i) {
if (obstacles[i] == currentLane + 1) {
int minJump = INT_MAX;
for (int lane = 0; lane < 3; ++lane) {
if (lane != currentLane && obstacles[i] != lane + 1) {
if (minJump > sideJumps) {
minJump = sideJumps + 1;
}
}
}
sideJumps = minJump;
currentLane = (currentLane + 1) % 3; // Switch lane
}
}
return sideJumps;
}
int main() {
int obstacles[] = {0, 1, 2, 3, 0};
int result = minSideJumps(obstacles, 5);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int MinSideJumps(int[] obstacles) {
int currentLane = 1;
int sideJumps = 0;
for (int i = 1; i < obstacles.Length; i++) {
if (obstacles[i] == currentLane + 1) {
int minJump = int.MaxValue;
for (int lane = 0; lane < 3; lane++) {
if (lane != currentLane && obstacles[i] != lane + 1) {
if (minJump > sideJumps) {
minJump = sideJumps + 1;
}
}
}
sideJumps = minJump;
currentLane = (currentLane + 1) % 3;
}
}
return sideJumps;
}
public static void Main() {
Solution solution = new Solution();
int[] obstacles = {0, 1, 2, 3, 0};
Console.WriteLine(solution.MinSideJumps(obstacles));
}
}The Python implementation reads obstacles in order, applying a greedy heuristic plus backtracking to adapt the correct path decisions and keep the transition minimum by avoiding any obstructive lanes as encountered.
Time Complexity: O(n), processing occurs once per element.
Space Complexity: O(1), no additional overhead apart from input.
Approach 3: Dynamic Programming
We define f[i][j] as the minimum number of sidesteps for the frog to reach the i-th point and be on the j-th lane (index starts from 0).
Note that the frog starts on the second lane (the problem index starts from 1), so the value of f[0][1] is 0, and the values of f[0][0] and f[0][2] are both 1. The answer is min(f[n][0], f[n][1], f[n][2]).
For each position i from 1 to n, we can enumerate the current lane j of the frog. If obstacles[i] = j + 1, it means that there is an obstacle on the j-th lane, and the value of f[i][j] is infinity. Otherwise, the frog can choose not to jump, in which case the value of f[i][j] is f[i - 1][j], or the frog can sidestep from other lanes, in which case f[i][j] = min(f[i][j], min(f[i][0], f[i][1], f[i][2]) + 1).
In the code implementation, we can optimize the first dimension of space and only use an array f of length 3 for maintenance.
The time complexity is O(n), where n is the length of the array obstacles. The space complexity is O(1).
function minSideJumps(obstacles: number[]): number {
const inf = 1 << 30;
const f = [1, 0, 1];
for (let i = 1; i < obstacles.length; ++i) {
for (let j = 0; j < 3; ++j) {
if (obstacles[i] == j + 1) {
f[j] = inf;
break;
}
}
const x = Math.min(...f) + 1;
for (let j = 0; j < 3; ++j) {
if (obstacles[i] != j + 1) {
f[j] = Math.min(f[j], x);
}
}
}
return Math.min(...f);
}func minSideJumps(obstacles []int) int {
f := [3]int{1, 0, 1}
const inf = 1 << 30
for _, v := range obstacles[1:] {
for j := 0; j < 3; j++ {
if v == j+1 {
f[j] = inf
break
}
}
x := min(f[0], min(f[1], f[2])) + 1
for j := 0; j < 3; j++ {
if v != j+1 {
f[j] = min(f[j], x)
}
}
}
return min(f[0], min(f[1], f[2]))
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the length of the |
| Greedy Approach with Backtracking | Time Complexity: O(n), processing occurs once per element. |
| Dynamic Programming | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Sideway Jumps easy or hard?
Minimum Sideway Jumps is considered a Medium difficulty problem on LeetCode. The challenge is identifying the correct state representation and updating lane costs efficiently without building a full DP table.
How to solve Minimum Sideway Jumps in O(n)?
Iterate through the obstacle array while maintaining a DP array of size three representing the minimum jumps to stay in each lane. If an obstacle blocks a lane, mark it as unreachable. Update other lanes by considering a side jump from the minimum of the remaining lanes plus one. This single pass achieves O(n) time and constant space.
What is the best approach for Minimum Sideway Jumps?
Dynamic programming with state compression is the most reliable approach. Track the minimum side jumps required for each of the three lanes and update them as you iterate through obstacles. This method runs in O(n) time and O(1) space and is the approach most commonly expected in technical interviews.
What data structure is used in Minimum Sideway Jumps?
The main data structure is a small array of size three representing the cost to remain in each lane. This array is updated during iteration over the obstacles list. The algorithm mainly combines array traversal with dynamic programming transitions.
What is the time complexity of Minimum Sideway Jumps?
The optimal solutions run in O(n) time where n is the number of positions in the obstacle array. Each position is processed once while updating the cost for the three lanes. Space complexity can be reduced to O(1) by storing only the current minimum jumps for each lane.
Minimum Sideway Jumps Python or Java solution approach?
Python and Java implementations usually follow the same dynamic programming idea. Maintain a three‑element array storing minimum side jumps for lanes 1–3, update it while scanning obstacles, and adjust costs when a lane becomes blocked. The algorithm runs in O(n) time and constant space.
Is Minimum Sideway Jumps asked at Google, Amazon, or Meta?
Minimum Sideway Jumps is a typical dynamic programming and greedy reasoning problem similar to questions used in interviews at companies like Amazon, Google, and Meta. It tests state transition thinking, optimization, and the ability to compress DP states.