Problems

# Matrix Zigzag Traversal

## Problem

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]`

## Solution

The example result can be achieved by `6` (` = m + n - 1`) linear scans:

``````1
2 5
9 6 3
4 7 10
11 8
12
``````

Let `i` be the number of scans, starting from `0`, the even scans are going up-right, while the odd scans are going down-left. The starting point of each scan:

`i % 2 == 0`(up-right): if `i < m`, there are more rows down below(like `9` in the example), start from the first element in row(`matrix[i][0]`) otherwise we've reached the end of `m` rows(like `11` in the example), so start from the last row but `i - m + 1` position(`matrix[m - 1][i - m + 1]`)

``````int x = i < m ? i : m - 1;
int y = i < m ? 0 : i - m + 1;
``````

`i % 2 == 1` (down-left): similar to the up-right case

``````int x = i < n ? 0 : i - n + 1;
int y = i < n ? i : n - 1;
``````

After we find the starting point, we can just keep moving util we reach the edge of the matrix.