1824. Minimum Sideway Jumps

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

Example: 2

Input: obstacles = [0,1,1,3,3,0]

Output: 0

Example: 3

Input: obstacles = [0,2,1,0,3,0]

Output: 2

Constraints:

• obstacles.length == n + 1
• 1 <= n <= 5 * 10 ^ 5
• 0 <= obstacles[i] <= 3
• obstacles[0] == obstacles[n] == 0

Step I (Making Observations):

• First thing we need to note here is when we go to the next index, it costs us 0 and when we go sideways it costs us 1.
• So it is optimal to go sideways only once, because it won't lead to unnecessary increase in our cost to reach our destination.
• The point here is: If we move to the RIGHT, we can move to any direction (UP, DOWN or RIGHT again).
• But if we move UP or DOWN we have only one choice, i.e to move RIGHT.
• Also we will mark all our obstacles as having cost of Integer.MAX_VALUE. Because of this even if we take a path having obstacle, it will definitely have max cost and will be discarded.

Step II (Solving the problem using Recursion):

• Now, we will implement the above mentioned scenarios in a straight-forward manner.

Solving using recursion (Will give TLE): long recur(int idx, int lane, int movedToSide, long[][][] dp) { // dp is the array in which we mark obstacles // lanes outside of range [0, 2] are ignored if(lane < 0 || lane > 2) { return Integer.MAX_VALUE; } // we have reached the last index // since we do not move anywhere from here // we return 0 if(idx == dp.length - 1) { return 0; } long min = Integer.MAX_VALUE; // moving RIGHT min = Math.min(min, recur(idx + 1, lane, 0, dp)); // checking if we have moved sideways in the previous step // if yes, then this step is ignored if(movedToSide == 0) { // we are moving sideways and so we will add 1 to our result min = Math.min(min, 1 + recur(idx, lane - 1, 1, dp)); min = Math.min(min, 1 + recur(idx, lane - 2, 1, dp)); min = Math.min(min, 1 + recur(idx, lane + 1, 1, dp)); min = Math.min(min, 1 + recur(idx, lane + 2, 1, dp)); } return min; }

Step III (Using DP: From TLE to Accepted):

• Now for every state [idx, lane, movedToSide] we might be recomputing them again and again during recursion.
• This can result into TLE.
• So what we will do is, after computing value of [idx, lane, movedToSide] we will store it into dp array mapping them by [idx, lane, movedToSide].
• This step is shown in code below.

Full Code (Java): class Solution { long[][][] dp; public int minSideJumps(int[] obstacles) { dp = new long[obstacles.length][3][2]; for(int i = 0; i < obstacles.length; i++) { if(obstacles[i] != 0) { dp[i][obstacles[i] - 1][0] = Integer.MAX_VALUE; dp[i][obstacles[i] - 1][1] = Integer.MAX_VALUE; } } // marking all unsolved [i, j, k] as -1 // -1 indicates that particular subproblem is not solved for(int i = 0; i < obstacles.length; i++) { for(int j = 0; j < 3; j++) { for(int k = 0; k < 2; k++) { if(dp[i][j][k] == 0) { dp[i][j][k] = -1; } } } } return (int) (recur(0, 1, 0, dp)); } long recur(int idx, int lane, int movedToSide, long[][][] dp) { if(lane < 0 || lane > 2) { return Integer.MAX_VALUE; } if(idx == dp.length - 1) { return 0; } // checking if we have solved this subproblem if(dp[idx][lane][movedToSide] != -1) { return dp[idx][lane][movedToSide]; } long min = Integer.MAX_VALUE; min = Math.min(min, recur(idx + 1, lane, 0, dp)); if(movedToSide == 0) { min = Math.min(min, 1 + recur(idx, lane - 1, 1, dp)); min = Math.min(min, 1 + recur(idx, lane - 2, 1, dp)); min = Math.min(min, 1 + recur(idx, lane + 1, 1, dp)); min = Math.min(min, 1 + recur(idx, lane + 2, 1, dp)); } // storing the result into dp array // for faster retrieval // without recomputation dp[idx][lane][movedToSide] = min; return min; } }