Check if it is possible to reach M from 0 by given paths | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void canReach0toM ( int a [ ] [ 2 ] , int n , int m ) { int rightMost [ m + 1 ] ; int dp [ 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 ] = max ( rightMost [ a1 ] , b1 ) ; } for ( int i = m ; i >= 0 ; i -- ) { dp [ i ] = i ; for ( int j = min ( m , rightMost [ i ] ) ; j > i ; j -- ) { dp [ i ] = max ( dp [ i ] , dp [ j ] ) ; } } if ( dp [ 0 ] >= m ) { cout << " Yes " ; } else { cout << " No " ; } } 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 ; }