LeetCode 1824: Minimum Sideway Jumps
Problem Description
Explanation
To solve this problem, we can use dynamic programming. We can define a 2D dp array where dp[i][j] represents the minimum number of side jumps needed to reach lane j at point i. We initialize the dp array with a very large value except for dp[0][1] which is 0 since the frog starts at lane 2 point 0. We then iterate through the points and lanes, updating the dp values based on the previous points and lanes. At each point, we check if there is an obstacle and update the dp values accordingly. The final answer will be the minimum value in the dp array at point n.
Time complexity: O(n) where n is the number of points on the road. Space complexity: O(n) for the dp array.
Solutions
class Solution {
public int minSideJumps(int[] obstacles) {
int n = obstacles.length - 1;
int[][] dp = new int[n + 1][4];
Arrays.fill(dp[0], Integer.MAX_VALUE);
dp[0][1] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
for (int j = 1; j <= 3; j++) {
if (obstacles[i] != j) {
dp[i][j] = dp[i - 1][j];
}
}
for (int j = 1; j <= 3; j++) {
if (obstacles[i] != j) {
for (int k = 1; k <= 3; k++) {
if (obstacles[i] != k) {
if (j != k) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + 1);
}
}
}
}
}
}
return Math.min(dp[n][1], Math.min(dp[n][2], dp[n][3]));
}
}Loading editor...