# Matrix Zigzag Traversal

## Question

Given a matrix of m x n elements (m rows, n columns),
return all elements of the matrix in ZigZag-order.

Example
Given a matrix:

[
[1, 2,  3,  4],
[5, 6,  7,  8],
[9,10, 11, 12]
]
return [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]


## 题解

(0, 0)
(0, 1), (1, 0)
(2, 0), (1, 1), (0, 2)
(0, 3), (1, 2), (2, 1)
(2, 2), (1, 3)
(2, 3)


### Java - valid matrix index second

public class Solution {
/**
* @param matrix: a matrix of integers
* @return: an array of integers
*/
public int[] printZMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) return null;

int m = matrix.length - 1, n = matrix[0].length - 1;
int[] result = new int[(m + 1) * (n + 1)];
int index = 0;
for (int i = 0; i <= m + n; i++) {
if (i % 2 == 0) {
for (int x = i; x >= 0; x--) {
// valid matrix index
if ((x <= m) && (i - x <= n)) {
result[index] = matrix[x][i - x];
index++;
}
}
} else {
for (int x = 0; x <= i; x++) {
if ((x <= m) && (i - x <= n)) {
result[index] = matrix[x][i - x];
index++;
}
}
}
}

return result;
}
}


### Java - valid matrix index first

public class Solution {
/**
* @param matrix: a matrix of integers
* @return: an array of integers
*/
public int[] printZMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) return null;

int m = matrix.length - 1, n = matrix[0].length - 1;
int[] result = new int[(m + 1) * (n + 1)];
int index = 0;
for (int i = 0; i <= m + n; i++) {
int upperBoundx = Math.min(i, m); // x <= m
int lowerBoundx = Math.max(0, i - n); // lower bound i - x(y) <= n
int upperBoundy = Math.min(i, n); // y <= n
int lowerBoundy = Math.max(0, i - m); // i - y(x) <= m
if (i % 2 == 0) {
// column increment
for (int y = lowerBoundy; y <= upperBoundy; y++) {
result[index] = matrix[i - y][y];
index++;
}
} else {
// row increment
for (int x = lowerBoundx; x <= upperBoundx; x++) {
result[index] = matrix[x][i - x];
index++;
}
}
}

return result;
}
}