1.

You are given a 2-D array of size N x N. You have to print the elements of the array in diagonal order as shown below

Answer»

So, we have travelled the upper triangular half of the matrix diagonally. We can clearly see that the first diagonal has row = col i.e. the gap between them is 0. In the next diagonal, the column index is always greater than the row index by 1. The max gap up to which we can go is N-1, where N is the number of columns. So, we will use this gap strategy to traverse the matrix diagonally as shown below.

Java Code for Diagonal Traversal

import java.util.*;

public class Main {

public static void main(String[] args) throws Exception {
// write your code here
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();

int[][] mat = new int[n][n];

for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
mat[i][j] = scn.nextInt();
}
}

diagonalTraversal(mat);
}

public static void diagonalTraversal(int[][] mat) {

int maxGap = mat[0].length - 1;

for(int gap=0;gap<=maxGap;gap++) {

for(int i=0,j=gap;i<mat.length && j<mat[0].length;i++,j++) {
System.out.print(mat[i][j] + " ");
}
System.out.println();
}
}

}

Sample Output

Input:
5
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

Output:
1 7 13 19 25
2 8 14 20
3 9 15
4 10
5


  • Time Complexity: O(N2) as we have to traverse half matrix of size N x N.


  • Auxiliary Space: O(1) is the auxiliary space.


Discussion

No Comment Found

Related InterviewSolutions