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;
}
};
Difficulty
and has an acceptance rate of about 57% (4+ million submissions).
Typical patterns to solve this problem:
- Array
- Matrix
- Simulation
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 59: Spiral Matrix II
Solved On The Same Day
- problem 13: Roman to Integer
- problem 21: Merge Two Sorted Lists
- problem 28: Find the Index of the First Occurrence in a String
- problem 35: Search Insert Position
- problem 58: Length of Last Word
- problem 66: Plus One
- problem 67: Add Binary
- problem 69: Sqrt(x)
- problem 70: Climbing Stairs
- problem 206: Reverse Linked List
- problem 242: Valid Anagram
- problem 278: First Bad Version
- problem 283: Move Zeroes
- problem 367: Valid Perfect Square
- problem 374: Guess Number Higher or Lower
- problem 389: Find the Difference
- problem 441: Arranging Coins
- problem 459: Repeated Substring Pattern
- problem 509: Fibonacci Number
- problem 657: Robot Return to Origin
- problem 682: Baseball Game
- problem 704: Binary Search
- problem 709: To Lower Case
- problem 744: Find Smallest Letter Greater Than Target
- problem 746: Min Cost Climbing Stairs
- problem 860: Lemonade Change
- problem 896: Monotonic Array
- problem 976: Largest Perimeter Triangle
- problem 1137: N-th Tribonacci Number
- problem 1232: Check If It Is a Straight Line
- problem 1275: Find Winner on a Tic Tac Toe Game
- problem 1351: Count Negative Numbers in a Sorted Matrix
- problem 1491: Average Salary Excluding the Minimum and Maximum Salary
- problem 1502: Can Make Arithmetic Progression From Sequence
- problem 1523: Count Odd Numbers in an Interval Range
- problem 1539: Kth Missing Positive Number
- problem 1572: Matrix Diagonal Sum
- problem 1672: Richest Customer Wealth
- problem 1768: Merge Strings Alternately
- problem 1822: Sign of the Product of an Array
- problem 2: Add Two Numbers
- problem 5: Longest Palindromic Substring
- problem 33: Search in Rotated Sorted Array
- problem 34: Find First and Last Position of Element in Sorted Array
- problem 43: Multiply Strings
- problem 50: Pow(x, n)
- problem 62: Unique Paths
- problem 63: Unique Paths II
- problem 64: Minimum Path Sum
- problem 73: Set Matrix Zeroes
- problem 74: Search a 2D Matrix
- problem 120: Triangle
- problem 139: Word Break
- problem 153: Find Minimum in Rotated Sorted Array
- problem 198: House Robber
- problem 221: Maximal Square
- problem 275: H-Index II
- problem 279: Perfect Squares
- problem 300: Longest Increasing Subsequence
- problem 436: Find Right Interval
- problem 445: Add Two Numbers II
- problem 528: Random Pick with Weight
- problem 540: Single Element in a Sorted Array
- problem 611: Valid Triangle Number
- problem 658: Find K Closest Elements
- problem 852: Peak Index in a Mountain Array
- problem 981: Time Based Key-Value Store
- problem 1041: Robot Bounded In Circle
- problem 1146: Snapshot Array
- problem 2300: Successful Pairs of Spells and Potions
- problem 154: Find Minimum in Rotated Sorted Array II
Extra
- 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