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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Sideway Jumps

Number: 1952

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, Google, Pony.ai

Problem Description

A frog is trying to cross a 3-lane road from point 0 to point n. The frog starts at lane 2 and can move forward (from point i to i+1) in the same lane as long as there is no obstacle. Obstacles are represented by an array where obstacles[i] (with a value between 0 and 3) indicates that there is an obstacle on that specific lane at point i (if non-zero). The frog can also perform side jumps at the same point (to any other lane) if the destination lane does not have an obstacle. The goal is to find the minimum number of side jumps required to reach point n (in any lane).

Key Insights

  • Use dynamic programming to track the minimum side jumps required to reach each lane at the current point.
  • At the start, the frog is at lane 2 with 0 side jumps; lanes 1 and 3 initially require 1 side jump.
  • At each point, if an obstacle exists in a lane, that lane is temporarily inaccessible.
  • For each valid lane at that point, update the minimum side jumps by considering potential side jumps from the other lanes.
  • The final answer is the minimum side jumps among all lanes at the destination point.

Space and Time Complexity

Time Complexity: O(n) – Each point along the road is processed with a constant amount of work. Space Complexity: O(1) – Only a constant amount of extra space is used to store the current state across 3 lanes.

Solution

We can solve the problem using dynamic programming by maintaining an array of length 3 (one for each lane) that records the minimum number of side jumps needed to reach a given point in that lane. At the beginning, since the frog starts at lane 2, initialize the cost for lane 2 as 0 and the cost for lanes 1 and 3 as 1 (because only one side jump is needed to start in those lanes).

For every subsequent point along the road:

  1. If an obstacle is present on a lane at this point, mark the cost for that lane as infinity (or a very large number) since it is not accessible.
  2. Update the costs for the lanes by considering a possible side jump from every other lane at the same point. If moving sideways from lane i to lane j reduces the cost in lane j, update lane j’s cost to be the minimum of its current value or the cost in lane i plus one.
  3. Continue this process until reaching point n.
  4. The minimum cost among all lanes at point n is the answer.

This approach ensures that we always consider the best possible side jump strategy at every step.

Code Solutions

def minSideJumps(obstacles):
    n = len(obstacles) - 1
    # dp holds the minimum side jumps needed to reach current point in each lane:
    # lanes are 1-indexed; we use 0-indexed array: dp[0] for lane1, dp[1] for lane2, dp[2] for lane3.
    # Initialize: lane2 (dp[1]) = 0 since frog starts there, others = 1.
    dp = [1, 0, 1]
    for pos in range(1, n + 1):
        # Mark the lane with an obstacle as unreachable (infinite cost)
        if obstacles[pos] > 0:
            dp[obstacles[pos] - 1] = float('inf')
        # Update each lane cost by trying side jumps from other lanes
        for lane in range(3):
            # If this lane is accessible, try to update the other lanes.
            if obstacles[pos] != lane + 1:
                # Take the minimum side jump value possibly updated from any other lane.
                for other in range(3):
                    if other != lane:
                        dp[lane] = min(dp[lane], dp[other] + 1)
        # dp now contains the minimal side jumps to reach this position in each lane.
    return min(dp)

# Example usage:
print(minSideJumps([0,1,2,3,0]))  # Expected output: 2
← Back to All Questions