Minimum change in lanes required to cross all barriers

0 0 5 minutes read

Consider a 3 lane road of length N which includes (N + 1) points from 0 to N. A man starts at point 0 in the 2nd lane and wants to reach point N, but it is possible that there could be a barrier along the way. Given an array barrier[] of length (N + 1) where barrier[i](0 ? barrier[i] ? 3) defines a barrier on the lane at point i. If barrier[i] is 0, then there is no barrier at that point. Otherwise, there is a barrier at the barrier[i]^th lane at the i^th position. It is given that there will be at most one barrier in the 3 lanes at each point. The man can travel from i^th point to (i + 1)^th point only if there is no barrier at point (i + 1)^th point. To avoid a barrier, that man just has to change to the lane where there is no barrier.

The task is to find the minimum number of changes in the lane made by the man to reach point N in any lane starting from point 0 and lane 2.

Examples:

Input: barrier[] = [0, 1, 0, 2, 3, 1, 2, 0]Output: 3
Explanation:
In the below image the green circle are the barriers and the optimal path is shown in the diagram and the change in lane is shown by green arrow:

Input: barrier[] = [0, 2, 0, 1, 3, 0]Output: 2

Approach: The given problem can be solved using Dynamic Programming as it follows both the properties of Optimal Substructure and Overlapping Subproblems. First of all, create an array arr[] of size 3 where

dp[0] = Minimum crosses require to reach Lane-1
dp[1] = Minimum crosses require to reach Lane-2
dp[2] = Minimum crosses require to reach Lane-3

If it meets a stone set dp[i] to a very large value, i.e., greater than 10⁵ and return the minimum value from dp[0], dp[1] and dp[2]. Follow the steps below to solve the problem:

Initialize an array dp[] with values {1, 0, 1}.
Iterate over the range [0, N] using the variable j and performing the following tasks:
- Initialize a variable, say val as barrier[j].
- If val is greater than 0, then set the value of dp[val – 1] as 10⁶.
- Iterate over the range [0, N] using the variable i and if the value of val is not equal to (i + 1), then set the value of dp[i] as the minimum of dp[i] or (dp[i + 1]%3 + 1) or (dp[i + 2]%3 + 1).
After completing the above steps, print the minimum of dp[0] or dp[1] or dp[2] as the resultant number of changes of lanes.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of changes of lane required
int minChangeInLane(int barrier[], int n)
{
    int dp[] = { 1, 0, 1 };
    for (int j = 0; j < n; j++) {
 
        // If there is a barrier, then
        // add very large value
        int val = barrier[j];
        if (val > 0) {
            dp[val - 1] = 1e6;
        }
 
        for (int i = 0; i < 3; i++) {
 
            // Add the minimum value to
            // move forward with or
            // without crossing barrier
            if (val != i + 1) {
                dp[i] = min(dp[i],
                            min(dp[(i + 1) % 3],
                                dp[(i + 2) % 3])
                                + 1);
            }
        }
    }
 
    // Return the minimum value of
    // dp[0], dp[1] and dp[2]
    return min(dp[0], min(dp[1], dp[2]));
}
 
// Driver Code
int main()
{
    int barrier[] = { 0, 1, 2, 3, 0 };
    int N = sizeof(barrier) / sizeof(barrier[0]);
 
    cout << minChangeInLane(barrier, N);
 
    return 0;
}

Java

// Java program for the above approach
class GFG
{
 
// Function to find the minimum number
// of changes of lane required
static int minChangeInLane(int barrier[], int n)
{
    int dp[] = { 1, 0, 1 };
    for (int j = 0; j < n; j++) {
 
        // If there is a barrier, then
        // add very large value
        int val = barrier[j];
        if (val > 0) {
            dp[val - 1] = (int) 1e6;
        }
 
        for (int i = 0; i < 3; i++) {
 
            // Add the minimum value to
            // move forward with or
            // without crossing barrier
            if (val != i + 1) {
                dp[i] = Math.min(dp[i],
                            Math.min(dp[(i + 1) % 3],
                                dp[(i + 2) % 3])
                                + 1);
            }
        }
    }
 
    // Return the minimum value of
    // dp[0], dp[1] and dp[2]
    return Math.min(dp[0], Math.min(dp[1], dp[2]));
}
 
// Driver Code
public static void main(String[] args)
{
    int barrier[] = { 0, 1, 2, 3, 0 };
    int N = barrier.length;
 
    System.out.print(minChangeInLane(barrier, N));
 
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python program for the above approach
 
# Function to find the minimum number
# of changes of lane required
def minChangeInLane(barrier, n):
    dp = [1, 0, 1]
    for j in range(n):
 
        # If there is a barrier, then
        # add very large value
        val = barrier[j]
        if (val > 0):
            dp[val - 1] = 1000000
 
        for i in range(3):
 
            # Add the minimum value to
            # move forward with or
            # without crossing barrier
            if (val != i + 1):
                dp[i] = min(dp[i],
                            min(dp[(i + 1) % 3],
                                dp[(i + 2) % 3])
                            + 1)
    # Return the minimum value of
    # dp[0], dp[1] and dp[2]
    return min(dp[0], min(dp[1], dp[2]))
 
# Driver Code
barrier = [0, 1, 2, 3, 0]
N = len(barrier)
 
print(minChangeInLane(barrier, N))
 
# This code is contributed by subhammahato348.

C#

// C# program for the above approach
using System;
 
public class GFG
{
 
  // Function to find the minimum number
  // of changes of lane required
  static int minChangeInLane(int[] barrier, int n)
  {
    int []dp = { 1, 0, 1 };
    for (int j = 0; j < n; j++) {
 
      // If there is a barrier, then
      // add very large value
      int val = barrier[j];
      if (val > 0) {
        dp[val - 1] = (int) 1e6;
      }
 
      for (int i = 0; i < 3; i++) {
 
        // Add the minimum value to
        // move forward with or
        // without crossing barrier
        if (val != i + 1) {
          dp[i] = Math.Min(dp[i],
                           Math.Min(dp[(i + 1) % 3],
                                    dp[(i + 2) % 3])
                           + 1);
        }
      }
    }
 
    // Return the minimum value of
    // dp[0], dp[1] and dp[2]
    return Math.Min(dp[0], Math.Min(dp[1], dp[2]));
  }
 
  // Driver Code
  static public void Main (){
 
    // Code
    int []barrier = { 0, 1, 2, 3, 0 };
    int N = barrier.Length;
 
    Console.Write(minChangeInLane(barrier, N));
 
  }
}
 
// This code is contributed by Potta Lokesh

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the minimum number
// of changes of lane required
function minChangeInLane(barrier, n)
{
  let dp = [1, 0, 1];
  for (let j = 0; j < n; j++)
  {
   
    // If there is a barrier, then
    // add very large value
    let val = barrier[j];
    if (val > 0) {
      dp[val - 1] = 1e6;
    }
 
    for (let i = 0; i < 3; i++)
    {
     
      // Add the minimum value to
      // move forward with or
      // without crossing barrier
      if (val != i + 1) {
        dp[i] = Math.min(dp[i], Math.min(dp[(i + 1) % 3], dp[(i + 2) % 3]) + 1);
      }
    }
  }
 
  // Return the minimum value of
  // dp[0], dp[1] and dp[2]
  return Math.min(dp[0], Math.min(dp[1], dp[2]));
}
 
// Driver Code
let barrier = [0, 1, 2, 3, 0];
let N = barrier.length;
 
document.write(minChangeInLane(barrier, N));
 
// This code is contributed by _saurabh_jaiswal.
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!