Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1824.html
1824. Minimum Sideway Jumps
Level
Medium
Description
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:8
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 * 10^50 <= obstacles[i] <= 3obstacles[0] == obstacles[n] == 0
Solution
Use dynamic programming. Create a 2D array dp where dp[i][j] represents the minimum number of side jumps when reaching point i on lane j. Initially, dp[0][2] = 0 and dp[0][1] = dp[0][3] = 1. For 1 <= i <= n and 1 <= j <= 3, dp[i][j] = INFINITY if there is an obstacle at point i on lane j. Otherwise, dp[i][j] is obtained among the minimum of dp[i - 1][j] and dp[i][k] where 1 <= k <= 3 and j != k. Finally, return the minimum of dp[n].
-
class Solution { public int minSideJumps(int[] obstacles) { int n = obstacles.length - 1; final int INFINITY = n * 2; int[][] dp = new int[n + 1][4]; dp[0][1] = dp[0][3] = 1; for (int i = 1; i <= n; i++) { int obstacle = obstacles[i]; for (int j = 1; j <= 3; j++) dp[i][j] = dp[i - 1][j]; if (obstacle > 0) dp[i][obstacle] = INFINITY; for (int j = 1; j <= 3; j++) { if (j != obstacle) { for (int k = 1; k <= 3; k++) { if (j != k && k != obstacle) dp[i][j] = Math.min(dp[i][j], dp[i][k] + 1); } } } } int minJumps = Integer.MAX_VALUE; for (int i = 1; i <= 3; i++) minJumps = Math.min(minJumps, dp[n][i]); return minJumps; } } ############ 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])); } } -
// OJ: https://leetcode.com/problems/minimum-sideway-jumps/ // Time: O(N) // Space: O(N) class Solution { public: int minSideJumps(vector<int>& A) { int N = A.size(); vector<vector<int>> dp(N, vector<int>(3, -1)); for (int i = 0; i < 3; ++i) { dp[N - 1][i] = A[N - 1] == i + 1 ? -1 : 0; } for (int i = N - 2; i >= 0; --i) { int mn = INT_MAX; for (int j = 0; j < 3; ++j) { if (A[i] == j + 1 || A[i + 1] == j + 1) continue; mn = min(mn, dp[i][j] = dp[i + 1][j]); } if (A[i + 1] && A[i] != A[i + 1]) { dp[i][A[i + 1] - 1] = 1 + mn; } } return dp[0][1]; } }; -
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) ############ # 1824. Minimum Sideway Jumps # https://leetcode.com/problems/minimum-sideway-jumps/ class Solution: def minSideJumps(self, obs: List[int]) -> int: n = len(obs) lanes = [[True] * n for _ in range(3)] for i,x in enumerate(obs): if x != 0: lanes[x - 1][i] = False suffix = [[1] * n for _ in range(3)] for i in range(3): for j in reversed(range(n)): if not lanes[i][j]: suffix[i][j] = 0 else: if j != n - 1: suffix[i][j] += suffix[i][j + 1] curr = 1 jumps = 0 for i in range(n-1): if not lanes[curr][i+1]: lane1 = suffix[0][i] if curr != 0 and lanes[0][i] else float('-inf') lane2 = suffix[1][i] if curr != 1 and lanes[1][i] else float('-inf') lane3 = suffix[2][i] if curr != 2 and lanes[2][i] else float('-inf') m = max(lane1, lane2, lane3) if m == lane1: curr = 0 elif m == lane2: curr = 1 else: curr = 2 jumps += 1 return jumps -
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])) } func min(a, b int) int { if a < b { return a } return b } -
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); }