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 ith position. It is given that there will be at most one barrier in the 3 lanes at each point. The man can travel from ith 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 105 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 106.
- 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 requiredint 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 Codeint 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 approachclass GFG{// Function to find the minimum number// of changes of lane requiredstatic 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 Codepublic 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 requireddef 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 Codebarrier = [0, 1, 2, 3, 0]N = len(barrier)print(minChangeInLane(barrier, N))# This code is contributed by subhammahato348. |
C#
// C# program for the above approachusing 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 requiredfunction 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 Codelet barrier = [0, 1, 2, 3, 0];let N = barrier.length;document.write(minChangeInLane(barrier, N));// This code is contributed by _saurabh_jaiswal.</script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
