InterviewBit Academy is now Scaler!
InterviewBit Academy is now Scaler Academy!

Increasing Path in Matrix


Problem Description

Given a 2D integer matrix A of size N x M.

From A[i][j] you can move to A[i+1][j], if A[i+1][j] > A[i][j], or can move to A[i][j+1] if A[i][j+1] > A[i][j].

The task is to find and output the longest path length if we start from (0, 0).

NOTE:

  • If there doesn't exist a path return -1.


  • Problem Constraints

    1 <= N, M <= 103

    1 <= A[i][j] <= 108



    Input Format

    First and only argument is an 2D integer matrix A of size N x M.



    Output Format

    Return a single integer denoting the length of longest path in the matrix if no such path exists return -1.



    Example Input

    Input 1:

     A = [  [1, 2]
            [3, 4]
         ]
    

    Input 2:

     A = [  [1, 2, 3, 4]
            [2, 2, 3, 4]
            [3, 2, 3, 4]
            [4, 5, 6, 7]
         ]
    



    Example Output

    Output 1:

     3
    

    Output 2:

     7
    



    Example Explanation

    Explanation 1:

     Longest path is either 1 2 4 or 1 3 4.
    

    Explanation 2:

     Longest path is 1 2 3 4 5 6 7.
    



    NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
    Start solving Increasing Path in Matrix on Interview Code Editor
    Sign Up
    to access hints and editorial solutions for Increasing Path in Matrix
    Asked In:

    Discussion


    Loading...
    Click here to start solving coding interview questions