Question

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

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]


Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]


Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

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

• 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;
}
}

}

############

class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int top = 0, bottom = m - 1, left = 0, right = n - 1;
List<Integer> ans = new ArrayList<>();
while (left <= right && top <= bottom) {
for (int j = left; j <= right; ++j) {
}
for (int i = top + 1; i <= bottom; ++i) {
}
if (left < right && top < bottom) {
for (int j = right - 1; j >= left; --j) {
}
for (int i = bottom - 1; i > top; --i) {
}
}
++top;
--bottom;
++left;
--right;
}
return ans;
}
}

• // 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:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
ans = []
top, bottom, left, right = 0, m - 1, 0, n - 1
while left <= right and top <= bottom:
ans.extend([matrix[top][j] for j in range(left, right + 1)])
ans.extend([matrix[i][right] for i in range(top + 1, bottom + 1)])
if left < right and top < bottom:
ans.extend([matrix[bottom][j] for j in range(right - 1, left - 1, -1)])
ans.extend([matrix[i][left] for i in range(bottom - 1, top, -1)])
top, bottom, left, right = top + 1, bottom - 1, left + 1, right - 1
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]))]


• func spiralOrder(matrix [][]int) []int {
m, n := len(matrix), len(matrix[0])
ans := make([]int, 0, m*n)

top, bottom, left, right := 0, m-1, 0, n-1
for left <= right && top <= bottom {
for i := left; i <= right; i++ {
ans = append(ans, matrix[top][i])
}
for i := top + 1; i <= bottom; i++ {
ans = append(ans, matrix[i][right])
}
if left < right && top < bottom {
for i := right - 1; i >= left; i-- {
ans = append(ans, matrix[bottom][i])
}
for i := bottom - 1; i > top; i-- {
ans = append(ans, matrix[i][left])
}
}
top++
bottom--
left++
right--
}

return ans
}


• function spiralOrder(matrix: number[][]): number[] {
const m = matrix.length;
const n = matrix[0].length;
const res = [];
for (let i = 0; i <= m >> 1; i++) {
for (let j = i; j < n - i - 1; j++) {
res.push(matrix[i][j]);
}
for (let j = i; j < m - i - 1; j++) {
res.push(matrix[j][n - i - 1]);
}
for (let j = i; j < n - i - 1; j++) {
res.push(matrix[m - i - 1][n - j - 1]);
}
for (let j = i; j < m - i - 1; j++) {
res.push(matrix[m - j - 1][i]);
}
}
if (m & 1) {
res.push(matrix[m >> 1][n >> 1]);
}
return res.slice(0, m * n);
}


• /**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
let [top, bottom, left, right] = [0, m - 1, 0, n - 1];
let ans = [];
while (top <= bottom && left <= right) {
for (let j = left; j <= right; ++j) {
ans.push(matrix[top][j]);
}
for (let i = top + 1; i <= bottom; ++i) {
ans.push(matrix[i][right]);
}
if (left < right && top < bottom) {
for (let j = right - 1; j >= left; --j) {
ans.push(matrix[bottom][j]);
}
for (let i = bottom - 1; i > top; --i) {
ans.push(matrix[i][left]);
}
}
[top, bottom, left, right] = [top + 1, bottom - 1, left + 1, right - 1];
}
return ans;
};


• public class Solution {
public IList<int> SpiralOrder(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
int top = 0, bottom = m - 1, left = 0, right = n - 1;
var ans = new List<int>(m * n);
while (top <= bottom && left <= right)
{
for (int j = left; j <= right; ++j)
{
}
for (int i = top + 1; i <= bottom; ++i)
{
}
if (left < right && top < bottom)
{
for (int j = right - 1; j >= left; --j)
{
}
for (int i = bottom - 1; i > top; --i)
{
}
}
++top;
--bottom;
++left;
--right;
}
return ans;
}
}