# Minimum Sideway Jumps LeetCode Solution

Difficulty Level Medium

## Problem Statement

Minimum Sideway Jumps LeetCode Solution – 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 the point `i`. If `obstacles[i] == 0`, there are no obstacles at the point `i`. There will be at most one obstacle in the 3 lanes at each point.

• For example, if `obstacles == 1`, then there is an obstacle in 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 the 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 in 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`. ```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).```

## Explanation

If meet a stone, set its `dp[i]` to infinity.
result equals to `min(dp)`

## Code

### C++ Code For Minimum Sideway Jumps

```class Solution {
public:
int minSideJumps(vector<int>& A) {
int dp[] = {1, 0, 1};
for (int a: A) {
if (a > 0)
dp[a - 1] = 1e6;
for (int i = 0; i < 3; ++i)
if (a != i + 1)
dp[i] = min(dp[i], min(dp[(i + 1) % 3], dp[(i + 2) % 3]) + 1);
}
return min(dp, min(dp, dp));
}
};```

### Java Code For Minimum Sideway Jumps

```class Solution {
public int minSideJumps(int[] A) {
int[] dp = new int[]{1, 0, 1};
for (int a: A) {
if (a > 0)
dp[a - 1] = 1000000;
for (int i = 0; i < 3; ++i)
if (a != i + 1)
dp[i] = Math.min(dp[i], Math.min(dp[(i + 1) % 3], dp[(i + 2) % 3]) + 1);
}
return Math.min(dp, Math.min(dp, dp));
}
}```

### Python Code For Minimum Sideway Jumps

```class Solution:
def minSideJumps(self, A):
dp = [1, 0, 1]
for a in A:
if a:
dp[a - 1] = float('inf')
for i in range(3):
if a != i + 1:
dp[i] = min(dp[i], dp[(i + 1) % 3] + 1, dp[(i + 2) % 3] + 1)
return min(dp)
```

O(N)

O(1)

Translate »