# Question

Formatted question description: https://leetcode.ca/all/54.html

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

@tag-array


# Algorithm

Define p and q to be the height and width of the current loop. When p or q is 1, it means that the last loop has only one row or one column, and you can jump out of the loop. The difficulty of this question lies in the conversion of subscripts. How to correctly convert subscripts is the key to solving this problem. You can complete the subscripts by referring to the 3x3 example above.

# Code

Java

• import java.util.ArrayList;
import java.util.List;

public class Spiral_Matrix {

public class Solution {

List<Integer> list = new ArrayList<Integer>();

public List<Integer> spiralOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0)   return list;

int row = matrix.length;
int column = matrix[0].length;

int leftBoundary = 0, upBoundary = 1;
int rightBoundary = column - 1, downBoundary = row - 1; // marking boundary index

/*
direction: 1 is up, 2 is down, 3 is left, 4 is right
*/

// at beginning direction is right;
int direction = 4;
int i = 0, j = 0; // initial position of pointer

int count = 0;
while (count < row * column) { // @note: I see other solutions, with for() inside of while(), maybe a more intuitive way

// switch case
if (direction == 1) { // move right

if (i == upBoundary) {
direction = 4;
j++;

upBoundary++;

} else {
i--;
}
}

else if (direction == 2) {

if (i == downBoundary) {
direction = 3;
j--;

// update boundary
downBoundary--;
} else {
i++;
}
}

else if (direction == 3) {

if (j == leftBoundary) {
direction = 1;
i--;

// update boundary
leftBoundary++;

} else {
j--;
}
}

else { // direction == 4

// check boundary
if (j == rightBoundary) {
direction = 2;
i++;

// row boundary is 1 less now
rightBoundary--;
} else {
j++;
}

}
// end of direction switch-case

count++;
}

return list;
}
}

}

• // OJ: https://leetcode.com/problems/spiral-matrix
// Time: O(MN)
// Space: O(1)
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return {};
vector<int> ans;
int M = matrix.size(), N = matrix[0].size();
for (int i = 0; ans.size() < M * N; ++i) {
for (int j = i; j < N - i; ++j) ans.push_back(matrix[i][j]);
for (int j = i + 1; j < M - i; ++j) ans.push_back(matrix[j][N - i - 1]);
for (int j = N - i - 2; M - i - 1 != i && j >= i; --j) ans.push_back(matrix[M - i - 1][j]);
for (int j = M - i - 2; N - i - 1 != i && j > i; --j) ans.push_back(matrix[j][i]);
}
return ans;
}
};

• class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return []
ans = []
left, up, down, right = 0, 0, len(matrix) - 1, len(matrix[0]) - 1
while left <= right and up <= down:
for i in range(left, right + 1):
ans += matrix[up][i],
up += 1
for i in range(up, down + 1):
ans += matrix[i][right],
right -= 1
for i in reversed(range(left, right + 1)):
ans += matrix[down][i],
down -= 1
for i in reversed(range(up, down + 1)):
ans += matrix[i][left],
left += 1
return ans[:(len(matrix) * len(matrix[0]))]