This algorithm to print m*n matrix diagonally. Algorithm going to take Big O(m*n/2) time
Input :
|
1 2 3 4 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Output :
|
1 2 3 4 5 6 7 8 |
1 6 2 11 7 3 16 12 8 4 17 13 9 5 18 14 10 19 15 20 |
Below algorithm will take O(m*n/2) time.
Algorithm:
|
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 |
package com.omt.learn.algo; import com.omt.learn.algo.util.matrix.MatrixUtil; /** * Created by omt on 4/8/17. */ public class PrintMatrixDiagonally { public static void main(String... args) { int a[][] = MatrixUtil.createMatrix(4, 5); MatrixUtil.printMatrix(a); printMatrixDiagonally(a); } public static void printMatrixDiagonally(int matrix[][]) { StringBuilder sb = new StringBuilder(); StringBuilder sb3 = new StringBuilder(); for (int row = 0; row < matrix.length; row++) { StringBuilder sb2 = new StringBuilder(); int index = row; int lastRow = matrix.length - 1; int lastColumn = matrix[row].length - 1 - row; for (int column = 0; (row - column >= 0); column++) { sb.append(matrix[index][column]); sb.append(" "); if (lastColumn > 0 && (lastColumn + column) < matrix[row].length) { sb2.append(matrix[lastRow][lastColumn + column]); sb2.append(" "); lastRow--; } index--; } if (sb2.length() > 0) { sb2.append("\n"); } sb3.insert(0, sb2.toString()); sb.append("\n"); } System.out.print(sb.toString()); System.out.println(sb3.toString()); } } |