We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Sideway Jumps

Difficulty: Medium

Problem 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. 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. Return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2 at point 0.

Key Insights

  • The frog can only move forward if there are no obstacles on the current lane.
  • The frog can perform side jumps to another lane if it encounters an obstacle.
  • The challenge is to minimize the number of side jumps while reaching the end point.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a greedy approach. We will iterate through each point on the road and check the obstacles on the lanes. We will maintain the current lane and count the number of side jumps required. If an obstacle is encountered on the current lane, we will check the other lanes to see if a side jump is possible. The goal is to have the minimum number of side jumps by the time we reach point n. The data structure used here is simply an array to store the obstacles, and we will use a few variables to track the current lane and the number of side jumps.

Code Solutions

def minSideJumps(obstacles):
    n = len(obstacles) - 1
    # Initialize the minimum jumps required for each lane at the start
    jumps = [float('inf')] * 4
    jumps[2] = 0  # Starting at lane 2 with 0 jumps

    for i in range(n):
        for lane in range(1, 4):
            if obstacles[i] == lane:  # If there's an obstacle in this lane
                jumps[lane] = float('inf')  # No way to stay in this lane
            else:
                # If not an obstacle, we can move from the previous point
                jumps[lane] = min(jumps[lane], jumps[1] + (lane != 1), jumps[2] + (lane != 2), jumps[3] + (lane != 3))
        
        # Update the jumps for the next iteration
        new_jumps = [float('inf')] * 4
        for lane in range(1, 4):
            new_jumps[lane] = jumps[lane]
        jumps = new_jumps

    return min(jumps[1], jumps[2], jumps[3])
← Back to All Questions