Problem Description
Given an m x n matrix mat, return an array of all the elements of the array in a zigzag/diagonal order.
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
Solution
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
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;
class Program {
public static List<Integer> zigzagTraverse(List<List<Integer>> array) {
//Answer list
List<Integer> output = new ArrayList<>();
//Height of the matrix
int height = array.size() - 1;
//Width of the matrix
int width = array.get(0).size() - 1;
//We will be starting by doing downwards from the first element
boolean goingDown = true;
//Initialize the row, col to 0 to start with
int row = 0;
int col = 0;
//Check if the current row, col is within the bound of height and width of the matrix
while(isInbound(row, col, height, width)){
//"visit" the current element
output.add(array.get(row).get(col));
//Going Down
if(goingDown){
//If we are at the last row or first column, we cannot go diagonally down next
if(row == height || col == 0){
//So we change the direction
goingDown = false;
//If we are at the last row, we need to go right
if(row == height){
col++;
//If we are not at the last row (but the first column), we can go down
}else{
row++;
}
//Else, just go diagonally downwards
}else{
col--;
row++;
}
//Going Up
}else{
//If we are at the top most row or right most column, we cannot go diagonally upwards next
if(row == 0 || col == width){
//So, we change the direction
goingDown = true;
//If we are at the right most column, we need to go downwards
if(col == width){
row++;
//If we are not at the right most column, but we are at the top most row, we can go right
}else{
col++;
}
//Else, just go diagonally upwards
}else{
row--;
col++;
}
}
}
return output;
}
public static boolean isInbound(int row, int col, int h, int w){
if(row < 0 || row > h || col < 0 || col > w) return false;
return true;
}
}
If the first move is upwards
The only real change is the initial direction! That’s all.
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
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
int[] ans = new int[mat.length*mat[0].length];
int idx=0;
boolean goingDown = false; //Since we start moving upwards first, we set this to false
int height = mat.length-1;
int width = mat[0].length-1;
int row=0;
int col=0;
while(isInbound(row, col, height, width)){
ans[idx++] = mat[row][col];
if(goingDown){
if(row == height || col == 0){
goingDown = false;
if(row == height){
col++;
}else{
row++;
}
}else{
col--;
row++;
}
}else{
if(row == 0 || col == width){
goingDown = true;
if(col == width){
row++;
}else{
col++;
}
}else{
col++;
row--;
}
}
}
return ans;
}
public static boolean isInbound(int row, int col, int h, int w){
if(row < 0 || row > h || col < 0 || col > w) return false;
return true;
}
}