## Problem

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

## Solution

Code first:

vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> result; if (matrix.size() < 1) return result; int top = 0; int button = matrix.size() - 1; int left = 0; int right = matrix[0].size() - 1; while (top <= button && left <= right) { for (int x = left; x <= right; x++) { //left to right result.push_back(matrix[top][x]); } top++; for (int y = top; y <= button; y++) { //top to button result.push_back(matrix[y][right]); } right--; if (button >= top) { // check if the button line haven't been pushed for (int x = right; x >= left; x--) { result.push_back(matrix[button][x]); } button--; } if (right >= left) { //check if the left line haven't been pushed for (int y = button; y >= top; y--) { result.push_back(matrix[y][left]); } left++; } } return result; }

The solution is easy to understand, just iterate upper left -> upper right -> lower right -> lower -> left -> upper left. So we need four variable top, button, left, right to shrink to center step by step. The only tricky part is when we move from right to left and button to top, we should check if there are still space for this two operations. In fact, when I implement this, I debugged almost one hour and than find this.

Written with StackEdit.