Given a rectangular matrix mat of size n x m. The matrix may contain any integer values, and every row has the same number of columns. Return all elements of mat in clockwise spiral order starting from the top-left cell.
Example 1
Input: mat = [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20]]
Output: [1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12]
Explanation: The traversal first takes the top row, then the right column, then the bottom row in reverse, then the left column upward. The same pattern continues for the inner remaining matrix.
Example 2
Input: mat = [[1], [2], [3], [4]]
Output: [1, 2, 3, 4]
Explanation: The matrix has only one column, so the spiral order is the same as reading the column from top to bottom.
Optimal Approach
Spiral order always finishes the outer frame of the matrix before entering the smaller rectangle inside it. Once the top edge is printed, those cells should never be touched again. The same idea applies to the right edge, bottom edge, and left edge.
So the remaining work can be tracked by four boundaries: top, bottom, left, and right. After one side of the current frame is collected, that side is no longer part of the unvisited region, so its boundary moves inward.
This makes the traversal feel like peeling the matrix layer by layer. The only careful point is a thin remaining region. When the matrix shrinks to a single row or a single column, the bottom row or left column must be checked before collecting it, otherwise the same cells could be added twice.
Algorithm
If the matrix is empty or has no columns, return an empty list.
Initialize four boundaries around the full matrix: top row, bottom row, left column, and right column.
While the boundaries describe a valid remaining rectangle, collect the top row and shrink the top boundary, then collect the right column and shrink the right boundary.
If a row still remains, collect the bottom row from right to left and shrink the bottom boundary.
If a column still remains, collect the left column from bottom to top and shrink the left boundary.
Stop when the boundaries cross, then return the collected spiral order.
Dry Run
Spiral Matrix
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns matrix elements in clockwise spiral order. vector<int> spiralOrder(vector<vector<int>>& matrix) { // An empty matrix has no cells to traverse. if (matrix.empty() || matrix[0].empty()) { return {}; } vector<int> order; int top = 0; int bottom = matrix.size() - 1; int left = 0; int right = matrix[0].size() - 1; // Process one remaining rectangular layer at a time. while (top <= bottom && left <= right) { // Collect the current top row from left to right. for (int col = left; col <= right; col++) { order.push_back(matrix[top][col]); } top++; // Collect the current right column from top to bottom. for (int row = top; row <= bottom; row++) { order.push_back(matrix[row][right]); } right--; // A bottom row remains only if the top boundary has not crossed it. if (top <= bottom) { // Collect the current bottom row from right to left. for (int col = right; col >= left; col--) { order.push_back(matrix[bottom][col]); } bottom--; } // A left column remains only if the right boundary has not crossed it. if (left <= right) { // Collect the current left column from bottom to top. for (int row = bottom; row >= top; row--) { order.push_back(matrix[row][left]); } left++; } } return order; }};// Prints a one-dimensional integer list.void printVector(vector<int>& values) { cout << '['; // Print commas only between neighboring values. for (int index = 0; index < values.size(); index++) { // A comma is needed before every value except the first one. if (index > 0) { cout << ", "; } cout << values[index]; } cout << "]\n";}// Driver codeint main() { vector<vector<int>> matrix = { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20} }; // instance for class Solution Solution sol; vector<int> result = sol.spiralOrder(matrix); printVector(result); return 0;}Complexity Analysis
Time Complexity: O(n * m), because every matrix cell is appended once.
Space Complexity: O(1) auxiliary space, because only four boundaries and a few counters are stored. The returned list stores n * m elements.
Interview follow-up Questions
Boundary traversal touches each matrix cell exactly once and avoids a separate visited matrix. Since the output itself contains all n * m values, no algorithm can avoid reading every cell that must be printed.
Be the first to add a comment.