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:

1. Right ➡️: 1, 2, 3
2. Down ⬇️: 6, 9
3. Left ⬅️: 8, 7
4. Up ⬆️: 4
5. 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.