05 August 2008
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
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
// Check for empty matrices
if (matrix == null || matrix.length == 0) {
return new int[0];
}
// Variables to track the size of the matrix
int N = matrix.length;
int M = matrix[0].length;
// The two arrays as explained in the algorithm
int[] result = new int[N*M];
int k = 0;
ArrayList<Integer> intermediate = new ArrayList<Integer>();
// We have to go over all the elements in the first
// row and the last column to cover all possible diagonals
for (int d = 0; d < N + M - 1; d++) {
// Clear the intermediate array every time we start
// to process another diagonal
intermediate.clear();
// We need to figure out the "head" of this diagonal
// The elements in the first row and the last column
// are the respective heads.
int r = d < M ? 0 : d - M + 1;
int c = d < M ? d : M - 1;
// Iterate until one of the indices goes out of scope
// Take note of the index math to go down the diagonal
while (r < N && c > -1) {
intermediate.add(matrix[r][c]);
++r;
--c;
}
// Reverse even numbered diagonals. The
// article says we have to reverse odd
// numbered articles but here, the numbering
// is starting from 0 :P
if (d % 2 == 0) {
Collections.reverse(intermediate);
}
for (int i = 0; i < intermediate.size(); i++) {
result[k++] = intermediate.get(i);
}
}
return result;
}
}