Spiral Matrix

LeetCode 54 | Difficulty: Medium

Medium

Problem Description

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`

Topics: Array, Matrix, Simulation

---

Approach

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 165 ms)

Metric	Value
Runtime	165 ms
Memory	40.8 MB
Date	2022-02-10

Solution

public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
       var result = new List<int>();
    int startRow = 0, endRow = matrix.GetLength(0)-1, startCol = 0, endCol = matrix[0].GetLength(0)-1;
    
    while(startRow <= endRow && startCol <= endCol)
    {
        for (int i = startCol; i <= endCol; i++)
        {
            result.Add(matrix[startRow][i]);
        }
        for (int i = startRow+1; i <= endRow; i++)
        {
            result.Add(matrix[i][endCol]);
        }
        for (int i = endCol-1; i >= startCol; i--)
        {
            if(startRow == endRow) break;
            result.Add(matrix[endRow][i]);
        }
        for (int i = endRow-1; i >= startRow+1; i--)
        {
            if(startCol==endCol) break;
            result.Add(matrix[i][startCol]);
        }
        
        startRow++;
        endRow--;
        startCol++;
        endCol--;       
    }
    
    // Write your code here.
    return result;
    }
}

📜 1 more C# submission(s)

Submission (2017-11-06) — 542 ms, N/A

public class Solution {
    public IList<int> SpiralOrder(int[,] matrix) {
    int k = 0, l = 0, last_row = matrix.GetLength(0) - 1, last_col = matrix.GetLength(1)-1;
    if (last_col < 0 && last_row < 0) return new List<int>();
    
    var result = new List<int>();
    while (k <= last_row && l <= last_col)
    {
        for (int i = l; i <= last_col; i++)
        {
            result.Add(matrix[k,i]);
        }
        
        k++;
        for (int i = k; i <= last_row; i++)
        {
            result.Add(matrix[i,last_col]);
        }
        last_col--;

        if (k <= last_row)
        {
            for (int i = last_col; i >= l; i--)
            {
                result.Add(matrix[last_row, i]);
            }
        }
        last_row--;

        if (l <= last_col)
        {
            for (int i = last_row; i >= k; i--)
            {
                result.Add(matrix[i, l]);
            }
        }
        l++;

    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Well for some problems, the best way really is to come up with some algorithms for simulation. Basically, you need to simulate what the problem asks us to do.

Hint 2: We go boundary by boundary and move inwards. That is the essential operation. First row, last column, last row, first column, and then we move inwards by 1 and repeat. That's all. That is all the simulation that we need.

Hint 3: Think about when you want to switch the progress on one of the indexes. If you progress on i out of [i, j], you'll shift in the same column. Similarly, by changing values for j, you'd be shifting in the same row. Also, keep track of the end of a boundary so that you can move inwards and then keep repeating. It's always best to simulate edge cases like a single column or a single row to see if anything breaks or not.