Print All Possible Paths From Top Left Corner To Bottom Right Corner Of A 2-D Matrix
You are given an ‘M*N’ Matrix, You need to print all possible paths from its top left corner to the bottom right corner if given that you can either move right i.e from (i,j) to (i,j+1) or down i.e from (i, j) to (i+1, j).

For Example :

1 2 3 4 5 6 For the above 2*3 matrix , possible paths are (1 2 3 6) , (1 2 5 6) , (1 4 5 6).

Note :

You can return the paths in any order.

Input Format :

The first line contains two space-separated integers, ‘M’ and ‘N’ denoting the number of rows and columns of the given matrix. Each of the following ‘M’ lines contains N space-separated numbers.

Output Format :

Print all the paths in a new line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Print All Possible Paths From Top Left Corner To Bottom Right Corner Of A 2-D Matrix

You are given an ‘M*N’ Matrix, You need to print all possible paths from its top left corner to the bottom right corner if given that you can either move right i.e from (i,j) to (i,j+1) or down i.e from (i, j) to (i+1, j).

For Example :

1 2 3
4 5 6

For the above 2*3 matrix , possible paths are (1 2 3 6) , (1 2 5 6) , (1 4 5 6).

Note :

You can return the paths in any order.

Input Format :

The first line contains two space-separated integers, ‘M’ and ‘N’ denoting the number of rows and columns of the given matrix.

Each of the following ‘M’ lines contains N space-separated numbers.

Output Format :

Print all the paths in a new line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= M, N <= 10

Time Limit: 1 sec

Accepted Answer

Recursion

The basic idea to solve this problem is to use recursion. Recursively call function for next row ( row+1,col ) and next column ( row, col+1 ). If the row is equal to M-1 or the column is equal to N-1, then recursion is stopped.

Algorithm:

Take an array or vector ‘path’, which will store the path we have to print.
Start from the index (row, col) = (0,0).
Add mat(row, col) to ‘path.’
Recursively call for next row ( row+1, col ) and next column ( row, col+1 ).
If ‘row’ == ‘M-1’, it means we are at the last row and can go right only. Iterate from ( row, col) to ( row, N-1) and add elements to ‘path.’
Similarly, If ‘col’==’N-1’, it means we are at the last column and can go down only. Iterate from (row, col) to ( M-1, col) and add elements to the ‘path.’

Let us understand the above approach with the help of a recursion tree for the matrix given below

1 2 3

4 5 6

Output: 1 4 5 6

1 2 5 6

1 2 3 6

Space Complexity: OtherExplanation:

O(M+N).

Extra space used to store the path.

Time Complexity: OtherExplanation:

O(2^(M+N)), where M is the number of rows and N is the number of columns.

The minimum length from root to a leaf node in the recursion tree is min(M, N) and the maximum length is M+N. Therefore the total number of nodes is between 2^min(M, N) and 2^(M+N). Hence time complexity is O(2^(M+N)).

C++ (g++ 5.4)

/*

    Time Complexity : O(2^(M+N))

    Space Complexity :O(M+N)

    

    Where M,N are rows and columns of matrix.

*/



void findAllpaths(vector > &mat ,int row , int col, int m , int n , vector  & path , int cur,vector > &res )

{

    /*

       If we are at last row

       we can move right only

    */

    if(row == m-1)

    { 

        //Initialize vector to store path

        vector temp=path;

        

        //Push elements to temp.

        for(int i = col; i < n; i++)

        {

            temp.push_back(mat[row][i]);

        } 

        

        //Add this path to our result. 

        res.push_back(temp);

        return;

    }

    

    /*

       If we are at last column

       we can move down only

    */

    if( col==n-1 )

    {

        //Initialize vector to store path.

        vector temp=path;

        

        //Push elements to temp.

        for(int i = row; i < m; i++)

        {

            temp.push_back(mat[i][col]);

        } 

        

        //Add this path to our result. 

        res.push_back(temp);

        return;

    }

    

    // Push current element to the path list. 

     path.push_back(mat[row][col]); 

      

    /* 

       Recursively call findAllpaths

       for right direction(next row)

    */

    findAllpaths(mat, row+1, col , m, n, path, cur + 1,res); 

       

    /* 

       Recursively call findAllpaths

       for down direction(next column)

    */

    findAllpaths(mat, row, col+1, m, n, path, cur + 1,res);

    

    //Pop the Current element

    path.pop_back();

    

}



vector > printAllpaths(vector > & mat , int m , int n)

{

    //Vector to store the current path.

    vector path;

    

    //Store all the possible paths

    vector > ans;

    

    //Recursively call to find all paths.

    findAllpaths(mat, 0, 0, m, n, path, 0,ans); 

    

    return ans;

}

Java (SE 1.8)

/*

    Time Complexity : O(2^(M+N))

    Space Complexity :O(M+N)

    

    Where M,N are rows and columns of matrix.

*/



import java.util.ArrayList;



public class Solution 

{

    public static ArrayList path;

    public static ArrayList> res;



    public static void findAllpaths(int[][] mat ,int row , int col, int m , int n , int cur)

    {

        /*

           If we are at last row

           we can move right only

        */

        if(row == m-1)

        { 

            //Initialize vector to store path

            ArrayList temp = new ArrayList<>();

            for(int i=0 ; i            {

                temp.add(path.get(i));

            }

            

            //Push elements to temp.

            for(int i = col; i < n; i++)

            {

                temp.add(mat[row][i]);

            } 

            

            //Add this path to our result. 

            res.add(temp);

            return;

        }

        

        /*

           If we are at last column

           we can move down only

        */

        if( col==n-1 )

        {

            //Initialize vector to store path.

            ArrayList temp = new ArrayList<>();

            for(int i=0 ; i            {

                temp.add(path.get(i));

            }

            

            //Push elements to temp.

            for(int i = row; i < m; i++)

            {

                temp.add(mat[i][col]);

            } 

            

            //Add this path to our result. 

            res.add(temp);

            return;

        }

        

        // Push current element to the path list. 

         path.add(mat[row][col]); 

          

        /* 

           Recursively call findAllpaths

           for right direction(next row)

        */

        findAllpaths(mat, row+1, col , m, n, cur + 1); 

           

        /* 

           Recursively call findAllpaths

           for down direction(next column)

        */

        findAllpaths(mat, row, col+1, m, n, cur + 1);

        

        //Pop the Current element

        path.remove(path.size() - 1);



    }



    public static int[][] printAllPaths(int[][] mat, int m, int n) 

    {

        //Vector to store the current path.

        path = new ArrayList<>();

    

        //Store all the possible paths

        res = new ArrayList<>();

    

        //Recursively call to find all paths.

        findAllpaths(mat, 0, 0, m, n, 0);   



        int r = res.size();

        int c = res.get(0).size();

        int[][] ans = new int[r][c];

        for(int i=0 ; i        {

            for(int j=0; j            {

                ans[i][j] = res.get(i).get(j);

            }

        }

    

        return ans;

    }

}

Python (3.5)

"""

    Time Complexity : O(2^(M+N))

    Space Complexity :O(M+N)

    

    Where M,N are rows and columns of matrix.

"""



def printAllPathsUtil(mat, i, j, m, n, path, pi):

 

    # Reached the bottom of the matrix 

    # so we are left with only option to move right

    if (i == m - 1):

        for k in range(j, n):

            path[pi + k - j] = mat[i][k]

 

        for l in range(pi + n - j):

            print(path[l], end = " ")

        print()

        return

 

    # Reached the right corner of the matrix 

    # we are left with only the downward movement.

    if (j == n - 1):

 

        for k in range(i, m):

            path[pi + k - i] = mat[k][j]

 

        for l in range(pi + m - i):

            print(path[l], end = " ")

        print()

        return

 

    # Add the current cell 

    # to the path being generated

    path[pi] = mat[i][j]

 

    # Print all the paths 

    # that are possible after moving down

    printAllPathsUtil(mat, i + 1, j, m, n, path, pi + 1)

 

    

    printAllPathsUtil(mat, i, j + 1, m, n, path, pi + 1)

 

def printAllpaths(mat, m, n):

 

    path = [0 for i in range(m + n)]

    printAllPathsUtil(mat, 0, 0, m, n, path, 0)

You are given an ‘M*N’ Matrix, You need to print all possible paths from its top left corner to the bottom right corner if given that you can either move right i.e from (i,j) to (i,j+1) or down i.e from (i, j) to (i+1, j).

For Example :

Note :

Input Format :

Output Format :

Note :

Constraints :

Top JPMorgan Chase & Co. Machine Learning Engineer interview questions & answers

Popular interview questions of Machine Learning Engineer