Leetcode 54. Spiral Matrix
Problem Explanation
Given an m x n
2D array, or matrix (m rows, n columns), you have to return all elements of the array in spiral order.
Here's how the spiral order works: Starting from the top left corner (0,0) position of the matrix, you traverse the array to right, to bottom, then to the left and up, and keep continuing this inwards in a spiral manner.
For example, with input matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
, the output is [1,2,3,6,9,8,7,4,5]
which can be seen as going in the following order:
- Right โก๏ธ: 1, 2, 3
- Down โฌ๏ธ: 6, 9
- Left โฌ ๏ธ: 8, 7
- Up โฌ๏ธ: 4
- Right โก๏ธ: 5
Solution Approach
The implementation involves a simple iterative approach where four loops are used executing one loop at a time. These loops are responsible for the movement to right, bottom, left and upwards capturing elements at each cell. Four pointers/indexes (r1, c1, r2, c2) are maintained to keep track of the boundary of the circles (or quadrants) starting from outermost and gradually moving inward.
At each iteration, check if the output array size (ans.size()
) equals to total number of elements. If so, stop the process and return the output. This limiting condition is important for the matrices of the dimension like m > n
or n > m
, where without the check we would wrap around the matrix and start repeating numbers.
Boundaries are updated at each step.
Python Solution
1 2python 3class Solution: 4 def spiralOrder(self, matrix): 5 if not matrix: return [] 6 R, C = len(matrix), len(matrix[0]) 7 ans = [] 8 r1, r2 = 0, R-1 9 c1, c2 = 0, C-1 10 while len(ans) < R * C: 11 for c in range(c1, c2+1): 12 ans.append(matrix[r1][c]) 13 for r in range(r1+1, r2+1): 14 ans.append(matrix[r][c2]) 15 if r1 < r2 and c1 < c2: 16 for c in range(c2-1, c1, -1): 17 ans.append(matrix[r2][c]) 18 for r in range(r2, r1, -1): 19 ans.append(matrix[r][c1]) 20 r1 += 1 21 r2 -= 1 22 c1 += 1 23 c2 -= 1 24 return ans
JavaScript Solution
1 2javascript 3var spiralOrder = function(matrix) { 4 if (!matrix.length) return []; 5 const res = []; 6 7 let rowStart = 0, 8 rowEnd = matrix.length - 1, 9 colStart = 0, 10 colEnd = matrix[0].length - 1; 11 12 while (res.length < matrix.length * matrix[0].length) { 13 for (let i = colStart; i <= colEnd; i++) res.push(matrix[rowStart][i]); 14 for (let i = rowStart + 1; i <= rowEnd; i++) res.push(matrix[i][colEnd]); 15 if (rowStart < rowEnd && colStart < colEnd) { 16 for (let i = colEnd - 1; i > colStart; i--) res.push(matrix[rowEnd][i]); 17 for (let i = rowEnd; i > rowStart; i--) res.push(matrix[i][colStart]); 18 } 19 rowStart++; 20 rowEnd--; 21 colStart++; 22 colEnd--; 23 } 24 25 return res; 26};
Java solution
1 2java 3class Solution { 4 public List<Integer> spiralOrder(int[][] matrix) { 5 List<Integer> ans = new ArrayList(); 6 if(matrix.length == 0 || matrix[0].length == 0) return ans; 7 int n = matrix.length, m = matrix[0].length; 8 int i=0, j=0, di=0, dj=1; 9 for(int k=0; k<m*n; k++){ 10 ans.add(matrix[i][j]); 11 matrix[i][j] = 0; 12 if(matrix[(i+di+n)%n][(j+dj+m)%m] == 0){ 13 int temp = di; 14 di = dj; 15 dj = -temp; 16 } 17 i+=di; 18 j+=dj; 19 } 20 return ans; 21 } 22}
C++ Solution
1 2cpp 3class Solution { 4public: 5 vector<int> spiralOrder(vector<vector<int>>& matrix) { 6 if(matrix.empty() || matrix[0].empty()) return {}; 7 int m = matrix.size(), n = matrix[0].size(); 8 vector<int> res; 9 vector<vector<bool>> visited(m, vector<bool>(n, false)); 10 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 11 int dir = 1, x = 0, y = 0; 12 for(int i = 0; i < m * n; ++i) { 13 res.push_back(matrix[x][y]); 14 visited[x][y] = true; 15 int nx = x + dx[dir], ny = y + dy[dir]; 16 if(nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny]) { 17 dir = (dir + 1) % 4; 18 nx = x + dx[dir], ny = y + dy[dir]; 19 } 20 x = nx, y = ny; 21 } 22 return res; 23 } 24};
C# Solution
1 2csharp 3public class Solution { 4 public IList<int> SpiralOrder(int[][] matrix) { 5 List<int> list = new List<int>(); 6 if(matrix.Length==0||matrix[0].Length==0) return list; 7 8 int top = 0; 9 int bottom = matrix.Length-1; 10 int left = 0; 11 int right = matrix[0].Length-1; 12 13 while(true){ 14 for(int i=left;i<=right;i++) list.Add(matrix[top][i]); 15 if(++top>bottom) break; 16 for(int i=top;i<=bottom;i++) list.Add(matrix[i][right]); 17 if(--right<left) break; 18 for(int i=right;i>=left;i--) list.Add(matrix[bottom][i]); 19 if(--bottom<top) break; 20 for(int i=bottom;i>=top;i--) list.Add(matrix[i][left]); 21 if(++left>right) break; 22 } 23 24 return list; 25 } 26}
In each of these solutions, the program starts by looping through the first row of the matrix from left to right and then proceeds to the last column from top to bottom. It will then navigate through the last row from right to left and finally, it will run upwards through the first column. The process will then repeat itself in the next concentric internal matrix until all elements are traversed.
This systematic spiral traversal is maintained by incrementing and decrementing the defined boundaries and pointers/ranges of rows and columns:
-
In Python solution, the variables 'r1' and 'c1' point to start of row and column. 'r2' and 'c2' point to end of row and column. We start traversal from 'r1' and 'c1' and proceed until we reach 'r2' and 'c2'. After completion of a spiral loop, we increment ('r1' and 'c1') and decrement ('r2' and 'c2') the limits so that they point to the new boundary of the next inner spiral circle.
-
In JavaScript, similar variables are named as 'rowStart', 'rowEnd', 'colStart', 'colEnd'.
-
In Java, the looping process is followed in similar manner, with a slight variation of moving diagonal ('di', 'dj') and processing matrix crosswise.
-
In C++ and C#, the approach is similar, but instead of moving in a spiral, they execute the traversal in the clockwise direction from the extreme left top to right, top to bottom, right to left, bottom to top.
Regardless of the language, the main objective is to maintain the current traversal boundaries and move the pointers to cover all elements in the spiral order.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.