Problem 54

Abstract / Summary

Given a 2D grid of numbers return all elements in a spiral order starting from the top left corner

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 0054.cpp

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int size = matrix.size() * matrix[0].size();

        vector<int> result;
        result.reserve(size);

        int STOP = 9999;

        int dx = 1;
        int dy = 0;
        int x = 0;
        int y = 0;
        while (result.size() < size)
        {
            result.push_back(matrix[y][x]);
            matrix[y][x] = STOP;
            x += dx;
            y += dy;

            if (x < 0 || y < 0 || y >= matrix.size() || x >= matrix[0].size() || matrix[y][x] == STOP)
            {
                x -= dx;
                y -= dy;
                if      (dx == +1) { dx = 0; dy = +1; }
                else if (dx == -1) { dx = 0; dy = -1; }
                else if (dy == +1) { dx = -1; dy = 0; }
                else               { dx = +1; dy = 0; }
                x += dx;
                y += dy;
            }
        }

        return result;
    }
};
37 lines | 1003 bytes | submitted August 7, 2023 | GitHub   tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 57% (4+ million submissions).

Typical patterns to solve this problem:
  • Array
  • Matrix
  • Simulation
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The implementation generates a spiral ordering of a two-dimensional integer matrix. It walks the matrix in a clockwise spiral, collects each element into a result vector, and stops when every cell has been visited. The algorithm modifies the input matrix in place to mark visited cells, thereby avoiding auxiliary storage for a visitation map.

Initialization and Preallocation

int size = matrix.size() * matrix[0].size();

vector<int> result;
result.reserve(size);

The total number of elements is computed once and stored in size. The result vector is pre-allocated with reserve, guaranteeing that no reallocation occurs during the traversal. This eliminates the overhead of repeated memory allocations as the vector grows.

int STOP = 9999;

A sentinel value STOP is defined to replace visited entries. Because the algorithm only needs to detect whether a cell has been processed, any value that cannot appear in the original matrix works as a marker.

Main Traversal Loop

int dx = 1;
int dy = 0;
int x = 0;
int y = 0;
while (result.size() < size)
{
    result.push_back(matrix[y][x]);
    matrix[y][x] = STOP;
    x += dx;
    y += dy;

    if (x < 0 || y < 0 || y >= matrix.size() || x >= matrix[0].size() || matrix[y][x] == STOP)
    {
        x -= dx;
        y -= dy;
        // direction change logic follows
    }
}

The loop continues until the result vector contains size elements. Each iteration appends the current cell to result and immediately overwrites it with STOP. The coordinates are then advanced by the current direction vector (dx, dy). A boundary or visited-cell check follows; if the next step would leave the matrix or encounter a STOP, the algorithm backs up to the last valid cell and prepares to turn.

Direction Management

if      (dx == +1) { dx = 0; dy = +1; }
else if (dx == -1) { dx = 0; dy = -1; }
else if (dy == +1) { dx = -1; dy = 0; }
else               { dx = +1; dy = 0; }
x += dx;
y += dy;

The direction vectors encode the four cardinal movements: right (1,0), down (0,1), left (-1,0), and up (0,-1). When a turn is required, the code selects the next direction by examining the current dx and dy. After updating the direction, the coordinates are moved one step forward in the new direction, positioning the traversal at the next unvisited cell.

Edge Cases Handled

The algorithm gracefully processes matrices of various shapes. A single-row matrix causes the direction to switch from right to down immediately after the row ends, but the subsequent boundary check prevents any out-of-range access, terminating the loop after the row is exhausted. A single-column matrix follows a similar pattern, starting with a rightward step that immediately triggers a turn to down, then proceeds down the column. Rectangular matrices where the number of rows differs from the number of columns are handled without special casing; the boundary checks and STOP marker ensure that the spiral contracts correctly as the outer layers are consumed. The use of result.size() < size as the loop condition guarantees termination even when the matrix dimensions are minimal (e.g., 1×1).

Performance Optimizations

Precomputing the total element count and reserving the exact capacity for the result vector eliminates dynamic resizing overhead. In-place marking with the sentinel STOP removes the need for a separate boolean matrix, reducing memory consumption to O(1) auxiliary space. The direction change logic relies on simple integer comparisons and assignments, avoiding more expensive constructs such as modulo arithmetic or lookup tables. By performing the boundary and visited checks immediately after each step, the algorithm avoids unnecessary iterations and keeps the inner loop body minimal. These choices collectively produce a tight, cache-friendly traversal that operates with a single pass over the input matrix.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a big square made of smaller blocks with numbers inside them. The goal is to pick up all the numbers, one by one, by walking around the square like a spinning snail.

The code starts by figuring out how many blocks there are, so it knows when it has collected every single one. It keeps a list called result to store all the numbers it finds.

The person walking inside the square follows a simple rule. They keep moving forward in their current direction until they either hit a wall or a spot they have already visited. When that happens, they pretend they bumped into a corner and turn to the right to find a new path.

To keep track of where others have already been, every time a number is picked up, the spot is marked with a special number that tells the visitor to turn away next time. This keeps happening in a spiral pattern, going round and round towards the center, until there are no blocks left to pick up. Every time the person hits an edge, the tiny computer instructions choose a new way to go, like switching from going right to going down, then from down to left, then from left to up, and back again to right, until the whole square is cleared.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 6.19 | σ = 1.44

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python C# Java Rust JS Go TS
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++
chandansgowda Python
charles-wangkai Java
chenyanzhe C++
everthis JS
fartem Ruby
FelixFan1122 C#
fengvyi C++
gaosq0604 Python
Garvit244 Python
halfrost Go
haoel C++
JoshCrozier JS
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
lzl124631x C++
MacJim C++
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
fartem Ruby
FelixFan1122 C#
fengvyi C++
gaosq0604 Python
Garvit244 Python
halfrost Go
haoel C++
JoshCrozier JavaScript
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
lzl124631x C++
MacJim C++
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
57 links | 40 authors | 11 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Spiral Matrix - Microsoft Interview Question - Leetcode 54'
NeetCode 17 mins
Spiral Matrix - Microsoft Interview Question - Leetcode 54
YouTube video 'Spiral Matrix (LeetCode 54) | Full Solution with Visualizations | Study Algorithms'
Nikhil Lohia 14 mins
Spiral Matrix (LeetCode 54) | Full Solution with Visualizations | Study Algorithms
YouTube video 'Spiral Matrix - Leetcode 54 - Arrays & Strings (Python)'
Greg Hogg 9 mins
Spiral Matrix - Leetcode 54 - Arrays & Strings (Python)
YouTube video 'Spiral Matrix - LeetCode 54 - JavaScript'
AlgoJS 9 mins
Spiral Matrix - LeetCode 54 - JavaScript
YouTube video 'Spiral Matrix - LeetCode 54 - Coding Interview Questions'
One Code Man 5 mins
Spiral Matrix - LeetCode 54 - Coding Interview Questions
YouTube video 'Spiral Matrix - LeetCode 54 - Python #blind75 #leetcode #spiralmatrix'
Deepti Talesra 15 mins
Spiral Matrix - LeetCode 54 - Python #blind75 #leetcode #spiralmatrix
YouTube video '54  Spiral Matrix | Zero to FAANG Kunal | Assignment Solution | Leetcode'
Programmers Zone 29 mins
54 Spiral Matrix | Zero to FAANG Kunal | Assignment Solution | Leetcode
YouTube video 'LeetCode 54: Spiral Matrix - Interview Prep Ep 31'
Fisher Coder 17 mins
LeetCode 54: Spiral Matrix - Interview Prep Ep 31
YouTube video '[Java] Leetcode 54. Spiral Matrix [Array #4]'
Eric Programming 10 mins
[Java] Leetcode 54. Spiral Matrix [Array #4]
YouTube video 'Spiral Matrix | Leetcode 54 | Live coding session 🔥🔥🔥'
Coding Decoded 12 mins
Spiral Matrix | Leetcode 54 | Live coding session 🔥🔥🔥
YouTube video 'LeetCode 54: Spiral Matrix | C# Solution | Matrix Traversal |'
Code Scribbler 13 mins
LeetCode 54: Spiral Matrix | C# Solution | Matrix Traversal |
YouTube video 'Spiral Matrix - LeetCode 54 - Python Solution'
Code with Carter 8 mins
Spiral Matrix - LeetCode 54 - Python Solution
YouTube video '16. Spiral Matrix | Array - Medium | Learn DSA | Leetcode 54'
Ayushi Sharma 19 mins
16. Spiral Matrix | Array - Medium | Learn DSA | Leetcode 54
YouTube video '54 || Spiral Matrix || C++ || Leetcode Daily Challenge'
CodeFreaks 14 mins
54 || Spiral Matrix || C++ || Leetcode Daily Challenge
YouTube video 'LeetCode 54: Spiral Matrix | Java Solution | Matrix Traversal'
Code Scribbler 9 mins
LeetCode 54: Spiral Matrix | Java Solution | Matrix Traversal
YouTube video 'Daily Leetcode #1134: May 09, 2023 - 54. Spiral Matrix'
Programming Live with Larry 8 mins
Daily Leetcode #1134: May 09, 2023 - 54. Spiral Matrix
YouTube video 'LeetCode 54: Spiral Matrix | Python Solution | Matrix Traversal'
Code Scribbler 9 mins
LeetCode 54: Spiral Matrix | Python Solution | Matrix Traversal
YouTube video 'leetcode 54. Spiral Matrix - rotation matrix method and comments'
Code-Yao 10 mins
leetcode 54. Spiral Matrix - rotation matrix method and comments
YouTube video '54. Spiral Matrix | JavaScript | LeetCode Daily Challenge'
LeetCodeWithMonu 19 mins
54. Spiral Matrix | JavaScript | LeetCode Daily Challenge
YouTube video 'Spiral Matrix Python Solution - LeetCode #54'
Professor Oakes 5 mins
Spiral Matrix Python Solution - LeetCode #54
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

40 easy 30 medium 1 hard
72 solutions   August 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality