Check if it is possible to reach M from 0 by given paths
Given an array arr[] consisting of N pairs of integers, where each pair (a, b) represents a path from a to b, the task is to check if it is possible to reach M from 0 using the given paths in the array arr[]. If it is possible, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {{0, 2}, {2, 2}, {2, 5}, {4, 5}}, M = 5
Output: Yes
Explanation: It is possible to reach 5 from 0 using the pairs {(0, 2), (2, 5)}.Input: arr[] = {{0, 1}, {1, 2}, {2, 4}}, M = 5
Output: No
Approach: The given problem can be solved by finding the rightmost point from 0 by using the given array of path as a pair and then if the rightmost point is greater than equal to M that means there is a path between 0 to M. Otherwise, it is not. Follow the steps below to solve the problem:
- Initialize an array, say rightMost[] and dp[] that stores the farther point than can reach from 1 point and the farthest point respectively and initialize every value of rightMost[] with 0.
- Iterate over the range [0, N – 1] and update the rightMost[a[i][0]] as the maximum of rightMost[a[i][0]] and arr[i][1].
- Iterate over the range [M, 0] using the variable i:
- Update the value of dp[i] as i.
- Iterate over the range [min(m, rightMost[i]), i 1 ] using the variable j and update dp[i] as the maximum of dp[i] and dp[j].
- If the value of dp[0] is at least M, then it is possible to reach from 0 to M, therefore print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is // possible to reach M from 0 void canReach0toM( int a[][2], int n, int m) { // Stores the farther point that // can reach from 1 point int rightMost[m + 1]; // Stores the farthest point it // can go for each index i int dp[m + 1]; // Initialize rightMost[i] with 0 for ( int i = 0; i <= m; i++) { rightMost[i] = 0; } // Traverse the array for ( int i = 0; i < n; i++) { int a1 = a[i][0]; int b1 = a[i][1]; // Update the rightMost // position reached from a1 rightMost[a1] = max( rightMost[a1], b1); } for ( int i = m; i >= 0; i--) { dp[i] = i; // Find the farthest point // it can reach from i for ( int j = min(m, rightMost[i]); j > i; j--) { dp[i] = max(dp[i], dp[j]); } } // If point < can be reached if (dp[0] >= m) { cout << "Yes" ; } else { cout << "No" ; } } // Driver Code int main() { int arr[][2] = { { 0, 2 }, { 2, 2 }, { 2, 5 }, { 4, 5 } }; int M = 5; int N = sizeof (arr) / sizeof (arr[0]); canReach0toM(arr, N, M); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to check if it is // possible to reach M from 0 static void canReach0toM( int [][] a, int n, int m) { // Stores the farther point that // can reach from 1 point int [] rightMost = new int [m + 1 ]; // Stores the farthest point it // can go for each index i int [] dp = new int [m + 1 ]; // Initialize rightMost[i] with 0 for ( int i = 0 ; i <= m; i++) { rightMost[i] = 0 ; } // Traverse the array for ( int i = 0 ; i < n; i++) { int a1 = a[i][ 0 ]; int b1 = a[i][ 1 ]; // Update the rightMost // position reached from a1 rightMost[a1] = Math.max(rightMost[a1], b1); } for ( int i = m; i >= 0 ; i--) { dp[i] = i; // Find the farthest point // it can reach from i for ( int j = Math.min(m, rightMost[i]); j > i; j--) { dp[i] = Math.max(dp[i], dp[j]); } } // If point < can be reached if (dp[ 0 ] >= m) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } // Driver Code public static void main(String[] args) { int [][] arr = { { 0 , 2 }, { 2 , 2 }, { 2 , 5 }, { 4 , 5 } }; int M = 5 ; int N = arr.length; canReach0toM(arr, N, M); } } // This code is contributed by subhammahato348. |
Python3
# Python3 program for the above approach # Function to check if it is # possible to reach M from 0 def canReach0toM(a, n, m): # Stores the farther point that # can reach from 1 point rightMost = [ 0 for i in range (m + 1 )] # Stores the farthest point it # can go for each index i dp = [ 0 for i in range (m + 1 )] # Initialize rightMost[i] with 0 for i in range (m + 1 ): rightMost[i] = 0 # Traverse the array for i in range (n): a1 = a[i][ 0 ] b1 = a[i][ 1 ] # Update the rightMost # position reached from a1 rightMost[a1] = max (rightMost[a1], b1) i = m while (i > = 0 ): dp[i] = i # Find the farthest point # it can reach from i j = min (m, rightMost[i]) while (j > i): dp[i] = max (dp[i], dp[j]) j - = 1 i - = 1 # If point < can be reached if (dp[ 0 ] > = m): print ( "Yes" ) else : print ( "No" ) # Driver Code if __name__ = = '__main__' : arr = [ [ 0 , 2 ], [ 2 , 2 ], [ 2 , 5 ], [ 4 , 5 ] ] M = 5 N = len (arr) canReach0toM(arr, N, M) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approach using System; class GFG{ // Function to check if it is // possible to reach M from 0 static void canReach0toM( int [,] a, int n, int m) { // Stores the farther point that // can reach from 1 point int [] rightMost = new int [m + 1]; // Stores the farthest point it // can go for each index i int [] dp = new int [m + 1]; // Initialize rightMost[i] with 0 for ( int i = 0; i <= m; i++) { rightMost[i] = 0; } // Traverse the array for ( int i = 0; i < n; i++) { int a1 = a[i, 0]; int b1 = a[i, 1]; // Update the rightMost // position reached from a1 rightMost[a1] = Math.Max(rightMost[a1], b1); } for ( int i = m; i >= 0; i--) { dp[i] = i; // Find the farthest point // it can reach from i for ( int j = Math.Min(m, rightMost[i]); j > i; j--) { dp[i] = Math.Max(dp[i], dp[j]); } } // If point < can be reached if (dp[0] >= m) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } // Driver Code public static void Main() { int [,] arr = { { 0, 2 }, { 2, 2 }, { 2, 5 }, { 4, 5 } }; int M = 5; int N = arr.GetLength(0); canReach0toM(arr, N, M); } } // This code is contributed by code_hunt |
Javascript
<script> // JavaScript program for the above approach // Function to check if it is // possible to reach M from 0 function canReach0toM(a, n, m) { // Stores the farther point that // can reach from 1 point let rightMost = new Array(m + 1); // Stores the farthest point it // can go for each index i let dp = new Array(m + 1); // Initialize rightMost[i] with 0 for (let i = 0; i <= m; i++) { rightMost[i] = 0; } // Traverse the array for (let i = 0; i < n; i++) { let a1 = a[i][0]; let b1 = a[i][1]; // Update the rightMost // position reached from a1 rightMost[a1] = Math.max( rightMost[a1], b1); } for (let i = m; i >= 0; i--) { dp[i] = i; // Find the farthest point // it can reach from i for (let j = Math.min(m, rightMost[i]); j > i; j--) { dp[i] = Math.max(dp[i], dp[j]); } } // If point < can be reached if (dp[0] >= m) { document.write( "Yes" ); } else { document.write( "No" ); } } // Driver Code let arr = [[ 0, 2 ], [ 2, 2 ], [ 2, 5 ], [ 4, 5 ]]; let M = 5; let N = arr.length; canReach0toM(arr, N, M); </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us