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

	            list.add(matrix[i][j]);

	            // 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) {
                ans.add(matrix[top][j]);
            }
            for (int i = top + 1; i <= bottom; ++i) {
                ans.add(matrix[i][right]);
            }
            if (left < right && top < bottom) {
                for (int j = right - 1; j >= left; --j) {
                    ans.add(matrix[bottom][j]);
                }
                for (int i = bottom - 1; i > top; --i) {
                    ans.add(matrix[i][left]);
                }
            }
            ++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)
            {
                ans.Add(matrix[top][j]);
            }
            for (int i = top + 1; i <= bottom; ++i)
            {
                ans.Add(matrix[i][right]);
            }
            if (left < right && top < bottom)
            {
                for (int j = right - 1; j >= left; --j)
                {
                    ans.Add(matrix[bottom][j]);
                }
                for (int i = bottom - 1; i > top; --i)
                {
                    ans.Add(matrix[i][left]);
                }
            }
            ++top;
            --bottom;
            ++left;
            --right;
        }
        return ans;
    }
}

54 - Spiral Matrix

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions