# Minimum Sideway Jumps
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-sideway-jumps)
Canonical: https://scaleengineer.com/dsa/problems/minimum-sideway-jumps
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Pony.ai](https://scaleengineer.com/companies/pony.ai)
---
## 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** laneand 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:**

![](https://assets.glich.co/dsa/minimum-sideway-jumps/image0.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-sideway-jumps/image1.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-sideway-jumps/image2.png) 

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

# Approaches
## Recursion with Memoization (Top-Down DP)
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)`.
**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`.
**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 `StackOverflowError` for very large `n` due to deep recursion.; Slightly higher constant factor overhead compared to the iterative bottom-up approach.
### Explanation
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 from `solve(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 from `solve(point - 1, other_lane)`. A key detail is that the side jump from `other_lane` to `lane` at `point` is only possible if `other_lane` itself is not blocked by an obstacle at `point`.

The final answer is the minimum cost to reach point `n` on any of the three lanes.

```java
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;
    }
}
```
### Algorithm
1. Define a recursive function, say `solve(point, lane)`, which returns the minimum side jumps to reach `point` on the specified `lane`.
2. The state of our recursion is defined by the current point and the current lane.
3. Create a memoization table, `memo[point][lane]`, to store the results of subproblems to avoid re-computation.
4. **Base Case:** If `point == 0`, the frog is at the start. The cost is `0` for lane 2 and `1` for lanes 1 and 3 (one initial side jump).
5. **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)`. If `obstacles[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 from `point - 1`. It could have arrived by:
        i. Moving straight from `(point - 1, lane)`. The cost is `solve(point - 1, lane)`.
        ii. Moving from `(point - 1, other_lane)` to `(point, other_lane)` and then making a side jump to `lane`. The cost is `solve(point - 1, other_lane) + 1`. This is only possible if `other_lane` is not blocked at `point`.
    d. The minimum cost is the minimum of all valid possibilities from `point - 1`.
    e. Store the computed minimum cost in `memo[point][lane]` and return it.
6. The final answer is the minimum of `solve(n, 1)`, `solve(n, 2)`, and `solve(n, 3)`.

## Bottom-Up Dynamic Programming
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]`.
**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`.
**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.
### Explanation
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]`.

```java
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]));
    }
}
```
### Algorithm
1. Create a 2D DP table, `dp[n+1][4]`, where `dp[i][j]` stores the minimum side jumps to reach point `i` on lane `j`.
2. **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] = 1` and `dp[0][3] = 1`.
3. **Iteration:** Loop from `point i = 1` to `n`.
4. **Transitions:** For each `i`, calculate `dp[i][lane]` for all three lanes based on the values at `dp[i-1]`.
    a. If `obstacles[i] == lane`, then `dp[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 lane `k` at `i-1` and side-jumping at `i`: `dp[i-1][k] + 1`. This is only possible if lane `k` is not blocked at `i` (`obstacles[i] != k`).
5. **Final Result:** After filling the table up to `n`, the minimum jumps to reach point `n` is `min(dp[n][1], dp[n][2], dp[n][3])`.

## Space-Optimized Bottom-Up DP
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.
**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`.
**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.
### Explanation
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.

```java
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]));
    }
}
```
### Algorithm
1. Notice that the calculation for `dp[i]` only depends on the values from the immediately preceding point, `dp[i-1]`.
2. Instead of a 2D `dp` table, we can use a 1D array, say `dp` of size 4, to store the minimum jumps for the *current* point being processed.
3. **Initialization:** Initialize `dp` with the base case values for point 0: `dp[1]=1`, `dp[2]=0`, `dp[3]=1`.
4. **Iteration:** Loop from `point i = 1` to `n`.
    a. Inside the loop, create a temporary copy of the `dp` array, say `prev_dp`, which holds the values for point `i-1`.
    b. Calculate the new values for the `dp` array (representing point `i`) using the values from `prev_dp`.
    c. The transition logic is identical to the standard DP approach. For each `lane` at `i`, if it's not blocked, calculate its minimum cost based on `prev_dp`.
5. **Final Result:** After the loop finishes, the `dp` array holds the values for point `n`. The answer is `min(dp[1], dp[2], dp[3])`.

# Solutions
### Java

```java
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]));
  }
}

```

### CPP

```cpp
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]});
  }
};

```

### Python

```python
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)

```