If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
In this post, we will see how to print all paths from top left to bottom right of MxN matrix.
Problem
We need to print all paths from top left to bottom right of MxN matrix. You can either move down or right.
Solution
You can solve this problem using recursion.
Recursion
- We will pass row and column to track current row and column.
- paths will contain elements which we are going to print.
- Add current element to the path
- paths.add(matrix[row][column]);
- Go down by updating row to row+1
- matrixPathHelper(list, paths, matrix,row+1,column);
- Go right by updating column to column+1
- matrixPathHelper(list, paths, matrix,row,column+1);
- Once we are done, backtrack by removing last element from the list.
- paths.remove(paths.size() – 1);
- Base case 1:
- Once we reach to last row, we can only go right, so iterate from column to matrix[0].length and add elements to paths.
- Base case 2:
- Once we reach to last column, we can only go down, so iterate from row to matrix.length and add elements to paths.
Here is complete java program to print all paths from top left to bottom right of MxN matrix.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
package org.arpit.java2blog; import java.util.ArrayList; import java.util.List; public class PrintMatrixPaths { public static void main(String[] args) { PrintMatrixPaths cmp=new PrintMatrixPaths(); int[][] matrix= { {1,2,3}, {4,5,6}, {7,8,9} }; List<List<Integer>> printMatrixPaths = cmp.printMatrixPaths(matrix); System.out.println("Paths: "); for(List<Integer> list:printMatrixPaths) { System.out.println(list); } } public List<List<Integer>> printMatrixPaths(int [][] matrix) { List<List<Integer>> list = new ArrayList<>(); matrixPathsHelper(list, new ArrayList<Integer>(), matrix, 0,0); return list; } private void matrixPathsHelper(List<List<Integer>> list , List<Integer> paths, int [][] matrix, int row,int column){ // base case if(row==matrix.length -1) { ArrayList<Integer> pathsTemp=new ArrayList<>(paths); for (int i = column; i < matrix[0].length; i++) { pathsTemp.add(matrix[row][i]); } list.add(pathsTemp); return; } // base case if(column==matrix[0].length -1) { ArrayList<Integer> pathsTemp=new ArrayList<>(paths); for (int i = row; i < matrix.length; i++) { pathsTemp.add(matrix[i][column]); } list.add(pathsTemp); return; } // Add to list paths.add(matrix[row][column]); // Explore // go down matrixPathsHelper(list, paths, matrix,row+1,column); // go right matrixPathsHelper(list, paths, matrix,row,column+1); // Remove from list : backtrack paths.remove(paths.size() - 1); } } |
Output
Paths:
[1, 4, 7, 8, 9] [1, 4, 5, 8, 9] [1, 4, 5, 6, 9] [1, 2, 5, 8, 9] [1, 2, 5, 6, 9] [1, 2, 3, 6, 9]
[1, 4, 7, 8, 9] [1, 4, 5, 8, 9] [1, 4, 5, 6, 9] [1, 2, 5, 8, 9] [1, 2, 5, 6, 9] [1, 2, 3, 6, 9]
Here is diagram to illustrate recursion.
Please open above image in a new tab.
That’s all about how to print all paths from top left to bottom right of MxN matrix
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
