Check if it is possible to reach M from 0 by given paths | 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
def canReach0toM ( a , n , m ) : NEW_LINE INDENT rightMost = [ 0 for i in range ( m + 1 ) ] NEW_LINE dp = [ 0 for i in range ( m + 1 ) ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT rightMost [ i ] = 0 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT a1 = a [ i ] [ 0 ] NEW_LINE b1 = a [ i ] [ 1 ] NEW_LINE rightMost [ a1 ] = max ( rightMost [ a1 ] , b1 ) NEW_LINE DEDENT i = m NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT dp [ i ] = i NEW_LINE j = min ( m , rightMost [ i ] ) NEW_LINE while ( j > i ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , dp [ j ] ) NEW_LINE j -= 1 NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT if ( dp [ 0 ] >= m ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 0 , 2 ] , [ 2 , 2 ] , [ 2 , 5 ] , [ 4 , 5 ] ] NEW_LINE M = 5 NEW_LINE N = len ( arr ) NEW_LINE canReach0toM ( arr , N , M ) NEW_LINE DEDENT