Minimum Sideway Jumps — Solution in Python, Java & C++
Minimum Sideway Jumps solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Sideway Jumps is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A frog runs along a road with 3 lanes (numbered 1 to 3) and points 0 to n. It starts at point 0 in lane 2 and wants to reach point n in any lane.
obstacles has length n + 1: obstacles[i] is the lane blocked at point i, or 0 if point i is clear. At most one lane is blocked at any point, and points 0 and n are clear.
From point i in lane l the frog may hop forward to point i + 1 in the same lane if that spot is not blocked. It may also make a side jump: switch to any other lane at the same point (lanes need not be adjacent), as long as that lane is not blocked there.
Return the minimum number of side jumps needed to reach point n.
Example 1
Input: obstacles = [0,1,2,3,0]
Output: 2
Explanation: Lane 2 is blocked at point 2, so jump to lane 3 at point 1 (lane 1 is blocked there); lane 3 is blocked at point 3, so jump to lane 1 at point 2.
Example 2
Input: obstacles = [0,1,1,3,3,0]
Output: 0
Explanation: Lane 2 is never blocked.
Example 3
Input: obstacles = [0,2,0]
Output: 1
Constraints
obstacles.length == n + 11 <= n <= 5 * 10^50 <= obstacles[i] <= 3obstacles[0] == obstacles[n] == 0
Hints for Minimum Sideway Jumps
Hint 1
Track, for every point, the fewest side jumps needed to stand there in each of the three lanes.
Hint 2
Moving forward costs nothing, but a lane blocked at point
ibecomes unreachable there.Hint 3
At each point, any open lane can also be reached from the best lane at that point with one extra jump:
dp[l] = min(dp[l], min(dp) + 1).
How to solve Minimum Sideway Jumps
Keep three numbers — the minimum jumps to be in lane 1, 2 or 3 at the current point — and advance them point by point.
Approach
- At point 0:
dp = [1, 0, 1](lane 2 is free, the others cost one jump). - For each point
i = 1..n: if laneo = obstacles[i]is blocked, setdp[o] = ∞(the frog cannot be there). - Let
best = min(dp); for every lane not blocked ati,dp[l] = min(dp[l], best + 1). - Return
min(dp)at pointn.
Why it works
Carrying dp[l] forward is the free hop in the same lane, valid only when lane l is open at point i (otherwise it was set to ∞). A side jump at point i can reach any open lane from the cheapest position at point i, which costs min(dp) + 1; one jump per point is enough, because two jumps at the same point can always be replaced by a single jump to the final lane.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Side jumps are not restricted to adjacent lanes.
- Block the obstacle's lane before computing the minimum for side jumps at that point.
- Lanes are 1-indexed in the input but usually 0-indexed in code.
Reference solution
Python
from typing import List
def minSideJumps(obstacles: List[int]) -> int:
INF = 10**9
dp = [1, 0, 1]
for i in range(1, len(obstacles)):
o = obstacles[i]
if o:
dp[o - 1] = INF
best = min(dp)
for lane in range(3):
if o != lane + 1 and best + 1 < dp[lane]:
dp[lane] = best + 1
return min(dp)Java
public static int minSideJumps(int[] obstacles) {
final int INF = 1000000000;
int[] dp = {1, 0, 1};
for (int i = 1; i < obstacles.length; i++) {
int o = obstacles[i];
if (o > 0) dp[o - 1] = INF;
int best = Math.min(dp[0], Math.min(dp[1], dp[2]));
for (int lane = 0; lane < 3; lane++) {
if (o != lane + 1 && best + 1 < dp[lane]) dp[lane] = best + 1;
}
}
return Math.min(dp[0], Math.min(dp[1], dp[2]));
}C++
int minSideJumps(vector<int>& obstacles) {
const int INF = 1000000000;
int dp[3] = {1, 0, 1};
for (int i = 1; i < (int) obstacles.size(); i++) {
int o = obstacles[i];
if (o > 0) dp[o - 1] = INF;
int best = min(dp[0], min(dp[1], dp[2]));
for (int lane = 0; lane < 3; lane++) {
if (o != lane + 1 && best + 1 < dp[lane]) dp[lane] = best + 1;
}
}
return min(dp[0], min(dp[1], dp[2]));
}JavaScript
var minSideJumps = function(obstacles) {
var INF = 1000000000;
var dp = [1, 0, 1];
for (var i = 1; i < obstacles.length; i++) {
var o = obstacles[i];
if (o > 0) dp[o - 1] = INF;
var best = Math.min(dp[0], dp[1], dp[2]);
for (var lane = 0; lane < 3; lane++) {
if (o !== lane + 1 && best + 1 < dp[lane]) dp[lane] = best + 1;
}
}
return Math.min(dp[0], dp[1], dp[2]);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming