Check if it is possible to reach M from 0 by given paths | Java program for the above approach ; Function to check if it is possible to reach M from 0 ; Stores the farther point that can reach from 1 point ; Stores the farthest point it can go for each index i ; Initialize rightMost [ i ] with 0 ; Traverse the array ; Update the rightMost position reached from a1 ; Find the farthest point it can reach from i ; If point < can be reached ; Driver Code
import java . io . * ; class GFG { static void canReach0toM ( int [ ] [ ] a , int n , int m ) { int [ ] rightMost = new int [ m + 1 ] ; int [ ] dp = new int [ m + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) { rightMost [ i ] = 0 ; } for ( int i = 0 ; i < n ; i ++ ) { int a1 = a [ i ] [ 0 ] ; int b1 = a [ i ] [ 1 ] ; rightMost [ a1 ] = Math . max ( rightMost [ a1 ] , b1 ) ; } for ( int i = m ; i >= 0 ; i -- ) { dp [ i ] = i ; for ( int j = Math . min ( m , rightMost [ i ] ) ; j > i ; j -- ) { dp [ i ] = Math . max ( dp [ i ] , dp [ j ] ) ; } } if ( dp [ 0 ] >= m ) { System . out . print ( " Yes " ) ; } else { System . out . print ( " No " ) ; } } 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 ) ; } }