Sunday, December 21, 2014

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

Well, this is not a hard problem, the only thing I couldn't figure out last night was why the loop stops at 2 * count < rows. Actually, if we draw a spiral square, it's pretty clear.


Take this square as an example. Let's only look at the row for now. Because we goes in the order 0 -> 11 -> 2 -> 10 -> ... -> 5 ->6, so we always stops at the middle. It is the same with columns. Besides, if there is only one row or one column left (e.g., 3 by 3 matrix), we need to stop at the middle. 



public class SpiralMatrix {
    public ArrayList spiralOrder(int[][] matrix) {
        ArrayList rst = new ArrayList();
        if (matrix == null || matrix.length == 0)
            return rst;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int count = 0;
        //Need to use 2 * count instead of rows / 2
        //Otherwise will not work for rows or cols that are odd numbers       
        while (2 * count < rows && 2 * count < cols)
        {
            for (int j = count; j < cols - count; j++)
                rst.add(matrix[count][j]);
            for (int i = count + 1; i < rows - count; i++)
                rst.add(matrix[i][cols - count - 1]);
            if (2 * count == rows - 1 || 2 * count == cols - 1)
                break;
            for (int j = cols - count - 2; j >= count; j--)
                rst.add(matrix[rows - 1 - count][j]);
            for (int i = rows - 2 - count; i > count; i--)
                rst.add(matrix[i][count]);
            count++;
        }
        return rst;
    }
}

No comments:

Post a Comment