# Spiral Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/spiral-matrix)
Canonical: https://scaleengineer.com/dsa/problems/spiral-matrix
**Data structures:** Array, Matrix
**Companies:** [AMD](https://scaleengineer.com/companies/amd), [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Epic Systems](https://scaleengineer.com/companies/epic-systems), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Roblox](https://scaleengineer.com/companies/roblox), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Netflix](https://scaleengineer.com/companies/netflix), [Turing](https://scaleengineer.com/companies/turing), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [RBC](https://scaleengineer.com/companies/rbc), [Databricks](https://scaleengineer.com/companies/databricks), [Lenskart](https://scaleengineer.com/companies/lenskart), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo), [Trexquant](https://scaleengineer.com/companies/trexquant), [Anduril](https://scaleengineer.com/companies/anduril), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [WatchGuard](https://scaleengineer.com/companies/watchguard), [Darwinbox](https://scaleengineer.com/companies/darwinbox), [Nordstrom](https://scaleengineer.com/companies/nordstrom), [SIG](https://scaleengineer.com/companies/sig)
---
## Problem
Given an `m x n` `matrix`, return _all elements of the_ `matrix` _in spiral order_.

**Example 1:**

![](https://assets.glich.co/dsa/spiral-matrix/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/spiral-matrix/image1.jpg) 

**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`

# Approaches
## Simulation with Visited Matrix
This approach simulates the spiral traversal by keeping track of the current position (row, column) and the current direction of movement (right, down, left, up). To prevent visiting the same cell multiple times, we use an auxiliary boolean matrix of the same dimensions, `visited`, to mark cells that have already been added to the result.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Conceptually straightforward, as it directly simulates the path.; Easy to understand the logic of moving and turning.
**Cons:** Requires extra space proportional to the size of the matrix, which can be significant for large matrices.
### Explanation
The core idea is to walk the spiral path step by step. We start at the top-left corner `(0, 0)` and move right. We continue in one direction until we either hit the matrix boundary or a cell that we have already visited. When that happens, we turn right (e.g., from moving right to moving down) and continue. We repeat this process of moving and turning until we have visited all the cells in the matrix. A `visited` array is essential to keep track of our path and prevent infinite loops or incorrect traversals.

```java
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int[] dr = {0, 1, 0, -1}; // right, down, left, up
        int[] dc = {1, 0, -1, 0};
        int r = 0, c = 0, di = 0;

        for (int i = 0; i < rows * cols; i++) {
            result.add(matrix[r][c]);
            visited[r][c] = true;
            int nextR = r + dr[di];
            int nextC = c + dc[di];

            if (nextR >= 0 && nextR < rows && nextC >= 0 && nextC < cols && !visited[nextR][nextC]) {
                r = nextR;
                c = nextC;
            } else {
                di = (di + 1) % 4;
                r += dr[di];
                c += dc[di];
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` to store the spiral order elements.
- If the input matrix is empty, return the empty list.
- Get the dimensions of the matrix, `rows` and `cols`.
- Create a `visited` boolean matrix of size `rows x cols` and initialize all its elements to `false`.
- Define the four directions of movement using two arrays: `dr = {0, 1, 0, -1}` for row changes and `dc = {1, 0, -1, 0}` for column changes, corresponding to right, down, left, and up.
- Initialize the starting position `r = 0`, `c = 0`, and the initial direction index `di = 0`.
- Iterate `rows * cols` times, as we need to visit every element once.
    - Add the element `matrix[r][c]` to the `result` list.
    - Mark the current cell as visited: `visited[r][c] = true`.
    - Calculate the coordinates of the next cell in the current direction: `nextR = r + dr[di]`, `nextC = c + dc[di]`.
    - Check if the next cell is out of bounds or has already been visited.
    - If the next cell is invalid, change the direction by updating the direction index: `di = (di + 1) % 4`.
    - Update the current position `(r, c)` for the next iteration using the (possibly new) direction.
- Return the `result` list.

## Layer-by-Layer Traversal (Boundary Shrinking)
A more space-efficient approach is to view the matrix as a series of concentric layers or rectangles. We traverse the outermost layer, then shrink the boundaries to move to the next inner layer, and repeat this process until all elements are visited. This method avoids the need for an extra `visited` matrix.
**Time:** O(m * n) · **Space:** O(1)
**Pros:** Highly space-efficient, using only constant extra space.; Elegant solution that maps well to the problem's structure.
**Cons:** The logic for handling boundary conditions and edge cases (like single-row or single-column matrices) can be slightly more complex to implement correctly.
### Explanation
This approach works by maintaining four pointers: `top`, `bottom`, `left`, and `right`, which represent the boundaries of the current layer of the matrix we are traversing. In each iteration of a main loop, we perform four traversals:
1.  Move from `left` to `right` along the `top` boundary.
2.  Move from `top` to `bottom` along the `right` boundary.
3.  Move from `right` to `left` along the `bottom` boundary.
4.  Move from `bottom` to `top` along the `left` boundary.

After each full cycle, we 'shrink' the boundaries inwards (`top++`, `bottom--`, `left++`, `right--`) to define the next, smaller concentric rectangle. The process continues until the boundaries cross each other (`top > bottom` or `left > right`). Special checks are needed after the first two traversals to correctly handle matrices with a single row or column.

```java
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;

        while (top <= bottom && left <= right) {
            // Traverse Right
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // Traverse Down
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            if (top <= bottom) { // Check if there's a row to traverse left
                // Traverse Left
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) { // Check if there's a column to traverse up
                // Traverse Up
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- If the input matrix is empty, return the empty list.
- Initialize four pointers to define the boundaries of the current layer: `top = 0`, `bottom = matrix.length - 1`, `left = 0`, `right = matrix[0].length - 1`.
- Start a loop that continues as long as `top <= bottom` and `left <= right`.
    - **Traverse Right:** Iterate from `left` to `right` along the `top` row, adding `matrix[top][i]` to `result`. After this traversal, increment `top` to shrink the boundary.
    - **Traverse Down:** Iterate from `top` to `bottom` along the `right` column, adding `matrix[i][right]` to `result`. After this, decrement `right`.
    - **Check for single row/column cases:** Before traversing left and up, check if `top <= bottom` and `left <= right`. This is crucial to handle matrices that are just a single row or a single column, preventing elements from being added twice.
    - **Traverse Left:** Iterate from `right` to `left` (in reverse) along the `bottom` row, adding `matrix[bottom][i]` to `result`. Then, decrement `bottom`.
    - **Traverse Up:** Iterate from `bottom` to `top` (in reverse) along the `left` column, adding `matrix[i][left]` to `result`. Then, increment `left`.
- The loop terminates when the boundaries cross, and all layers have been traversed. Return the `result` list.

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < int > SpiralOrder(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        int[] dirs = new int[] {
            0,
            1,
            0,
            -1,
            0
        };
        IList < int > ans = new List < int > ();
        bool[, ] visited = new bool[m, n];
        for (int h = m * n, i = 0, j = 0, k = 0; h > 0; --h) {
            ans.Add(matrix[i][j]);
            visited[i, j] = true;
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x < 0 || x >= m || y < 0 || y >= n || visited[x, y]) {
                k = (k + 1) % 4;
            }
            i += dirs[k];
            j += dirs[k + 1];
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[] dirs = {0, 1, 0, -1, 0};
    int i = 0, j = 0, k = 0;
    List<Integer> ans = new ArrayList<>();
    boolean[][] vis = new boolean[m][n];
    for (int h = m * n; h > 0; --h) {
      ans.add(matrix[i][j]);
      vis[i][j] = true;
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y]) {
        k = (k + 1) % 4;
      }
      i += dirs[k];
      j += dirs[k + 1];
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @return {number[]} */ var spiralOrder =
  function (matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const ans = [];
    const vis = new Array(m).fill(0).map(() => new Array(n).fill(false));
    const dirs = [0, 1, 0, -1, 0];
    for (let h = m * n, i = 0, j = 0, k = 0; h > 0; --h) {
      ans.push(matrix[i][j]);
      vis[i][j] = true;
      const x = i + dirs[k];
      const y = j + dirs[k + 1];
      if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y]) {
        k = (k + 1) % 4;
      }
      i += dirs[k];
      j += dirs[k + 1];
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> spiralOrder(vector<vector<int>> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    int dirs[5] = {0, 1, 0, -1, 0};
    int i = 0, j = 0, k = 0;
    vector<int> ans;
    bool vis[m][n];
    memset(vis, false, sizeof(vis));
    for (int h = m * n; h; --h) {
      ans.push_back(matrix[i][j]);
      vis[i][j] = true;
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y]) {
        k = (k + 1) % 4;
      }
      i += dirs[k];
      j += dirs[k + 1];
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def spiralOrder ( self , matrix : List [ List [ int ]]) -> List [ int ]: m , n = len ( matrix ), len ( matrix [ 0 ]) dirs = ( 0 , 1 , 0 , - 1 , 0 ) i = j = k = 0 ans = [] vis = set () for _ in range ( m * n ): ans . append ( matrix [ i ][ j ]) vis . add (( i , j )) x , y = i + dirs [ k ], j + dirs [ k + 1 ] if not 0 <= x < m or not 0 <= y < n or ( x , y ) in vis : k = ( k + 1 ) % 4 i = i + dirs [ k ] j = j + dirs [ k + 1 ] return ans
```