{x}
blog image

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

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

1824. Minimum Sideway Jumps

Problem Description

A frog starts at point 0 in lane 2 and wants to reach point n on a 3-lane road. Obstacles are present on some lanes at certain points, represented by the obstacles array. The frog can move forward on its current lane if there's no obstacle, or it can make a side jump to any other lane at the same point (even if not adjacent), provided there's no obstacle in the target lane. The goal is to find the minimum number of side jumps needed to reach point n.

Solution: Dynamic Programming

This problem can be efficiently solved using dynamic programming. We'll use a DP array dp where dp[i] represents the minimum number of side jumps needed to reach lane i (0, 1, or 2) at the current point.

Initialization:

  • dp[0] = 1, dp[1] = 0, dp[2] = 1. The frog starts in lane 1 (index 1), so it takes 0 jumps to be there; it takes 1 jump to be in lanes 0 or 2.

Iteration:

We iterate through the obstacles array (excluding the first element as the frog starts at point 0). For each point i:

  1. Handle Obstacles: If there's an obstacle in lane j (obstacles[i] == j + 1), we set dp[j] = infinity. This prevents the frog from being in that lane at this point.

  2. Update DP Array: For each lane j without an obstacle, we update dp[j] as follows:

    • dp[j] = min(dp[j], min(dp[0], dp[1], dp[2]) + 1): This represents the possibility of a side jump from any lane to lane j. We take the minimum jumps from any lane, add 1 (for the side jump), and compare it with the current dp[j]. We take the minimum of the two values.
    • dp[j] = min(dp[j], dp[j]): The frog may choose not to jump and proceed along the current lane, this also needs to be taken into consideration.

Result:

After iterating through all points, the minimum of dp[0], dp[1], and dp[2] represents the minimum number of side jumps to reach point n.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the obstacles array. We iterate through the array once.
  • Space Complexity: O(1). We use a constant-size dp array (size 3).

Code Implementation (Python)

def minSideJumps(obstacles: list[int]) -> int:
    dp = [float('inf')] * 3  # Initialize dp array with infinity
    dp[1] = 0 #starting position
    for obstacle in obstacles[1:]:  # Start from the second element (point 1)
        if obstacle > 0:
            dp[obstacle - 1] = float('inf')  # Set dp[lane] to infinity if obstacle present
        for i in range(3):
            if obstacle != i + 1: #if there is no obstacle in current lane
                dp[i] = min(dp[i], min(dp[0], dp[1], dp[2]) + 1) #check for side jump
    return min(dp)

The code in other languages (Java, C++, Go, TypeScript) would follow a similar structure, with appropriate syntax changes for each language. The core logic of the dynamic programming algorithm remains the same.