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.

Code - Java

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;
        int n = matrix[0].length;
        int[] result = new int[n * m];
        int t = 0;

        for (int i = 0; i < n + m - 1; i++) {
            if (i % 2 == 1) {
                // down left
                int x = i < n ? 0 : i - n + 1;
                int y = i < n ? i : n - 1;
                while (x < m && y >= 0) {
                    result[t++] = matrix[x++][y--];
                }
            } else {
                // up right
                int x = i < m ? i : m - 1;
                int y = i < m ? 0 : i - m + 1;
                while (x >= 0 && y < n) {
                    result[t++] = matrix[x--][y++];
                }
            }
        }
        return result;
    }
}

Online Judge