Minimum Sideway Jumps

Medium
1484.

Minimum Sideway Jumps

Minimum Sideway Jumps is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon and Google interviews.

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 + 1
  • 1 <= n <= 5 * 10^5
  • 0 <= obstacles[i] <= 3
  • obstacles[0] == obstacles[n] == 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} obstacles
 * @return {number}
 */
var minSideJumps = function(obstacles) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 + 1
  • 1 <= n <= 5 * 10^5
  • 0 <= obstacles[i] <= 3
  • obstacles[0] == obstacles[n] == 0

Hints for Minimum Sideway Jumps

  1. Hint 1

    Track, for every point, the fewest side jumps needed to stand there in each of the three lanes.

  2. Hint 2

    Moving forward costs nothing, but a lane blocked at point i becomes unreachable there.

  3. 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

  1. At point 0: dp = [1, 0, 1] (lane 2 is free, the others cost one jump).
  2. For each point i = 1..n: if lane o = obstacles[i] is blocked, set dp[o] = ∞ (the frog cannot be there).
  3. Let best = min(dp); for every lane not blocked at i, dp[l] = min(dp[l], best + 1).
  4. Return min(dp) at point n.

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