Good morning! Here's our prompt for today.
Given an m * n
matrix array, can you print all its elements in a spiral order as shown in the figure below? Try to use only O(1)
space!

Constraints
- Total elements in the matrix <=
100000
- The values in the matrix ranges from
-1000000000
and1000000000
- Expected time complexity :
O(n*m)
wheren
andm
are the rows and columns respectively - Expected space complexity :
O(1)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
'PASSED: `spiraltraverse([[1,2,3,4], [5,6,7,8 ], [9,10,11,12], [13,14,15,16]])` should return `1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10`'
var assert = require('assert');
​
function spiraltraverse(inmatrix) {
// fill this in
}
​
try {
assert.equal(
spiraltraverse([
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
]),
'1,2,3,4,5,6,12,11,10,9,8,7'
);
​
console.log(
'PASSED: `spiraltraverse([[1,2,3,4,5,6], [7,8,9,10,11,12]])` should return `1,2,3,4,5,6,12,11,10,9,8,7 `'
);
} catch (err) {
console.log(err);
}
​
try {
assert.equal(
spiraltraverse([
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16],
Here's our guided, illustrated walk-through.
How do I use this guide?
Traversing the Matrix in Spiral Order
Let's begin solving with an example. Suppose we are given an m * n
matrix. The simplest way to traverse the matrix in spiral order is as shown in the figure below:

You can see the development of the traversal in 3
stages. We start at the top left corner, and traverse the outer rows and columns of the matrix and repeat the same on the inner rows and columns.
- First, there's the
yellow
outer ring portion. - Then, once we get to the
6
inmatrix[0][1]
, we encounter thegreen
portion. - Once we get to the
12
inmatrix[1][2]
, we finally are in the middle (and final) cell.
So we're building a bit of intuition now. This is how we get good at solving these types of interview questions! We are taking a complex problem and breaking it down. In this case, we essentially need to "transition" from the outer rings to inner. To do this, we'll need some variables for tracking when to make the switch.
colLower
and colUpper
variables keep track of the outer left and right columns, respectively. Also, rowLower
and rowUpper
keep track of the outer upper and bottom rows respectively of the matrix.
Traversing the Outer Edges
To traverse the outer edge, we have to follow the given sequence:
- Move right
- Move down
- Move left
- Move up
Once we have moved entirely right, we can increment rowLower
. Similarly, once we have traversed down the right-most column we can decrement colUpper
. Therefore, to traverse the entire matrix in spiral order, we can follow the given algorithm.
The entire process is shown in the figure below:

Here, we share some pseudo-code to help make sense of the logic involved.
xxxxxxxxxx
Method: traverse
Input: mxn matrix
​
Initialize:
1. rowLower = 0
2. rowUpper = m-1
3. colLower = 0
4. colUpper = n-1
​
while the entire matrix is not traversed repeat
{
i. Traverse the row with index rowLower
ii. rowLower ++
iii. Traverse the column with index colUpper
iv. colUpper --
v. Traverse the row with index rowUpper
vi. rowUpper --
vii. Traverse the column with index colLower
viii. colLower ++
}
Complexity of Spiral Traversal
The algorithm that traverses the matrix in spiral order visits each item of the matrix exactly once. As the matrix has m * n
entries, hence the time complexity is O(m * n)
.
We are using a fixed number of variables to solve the problem, and hence the space complexity is O(1)
.
Concluding Remarks
In this tutorial we have described a simple and easy to understand method for traversing any m * n
matrix in spiral order. The algorithm has linear time complexity in terms of the total entries of the matrix. When you implement your own routine for this traversal, your main challenge would be to make sure you don't exceed the bounds of the matrix and do not traverse any element more than once.
One Pager Cheat Sheet
- Print the elements of an
m * n
matrix array in a spiral order, usingO(1)
space andO(n*m)
time complexity, with all values between-1000000000
and1000000000
. - Traversing an
m * n
matrix in spiral order requires transitioning from the outer rings to the inner rings, while keeping track of the outer left and right columns, and the upper and bottom rows, withcolLower
,colUpper
,rowLower
, androwUpper
variables. - We can traverse an entire matrix in spiral order by following an algorithm of moving right, then down, then left, then up, and incrementing
rowLower
and decrementingcolUpper
after each iteration. - The algorithm to traverse an
m * n
matrix in spiral order has a linear time complexity and fixed space complexity ofO(1)
.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
}
var assert = require('assert');
​
function spiraltraverse(inmatrix) {
if (!inmatrix.length) return [];
const res = [];
const dirs = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0],
];
const scope = [inmatrix[0].length, inmatrix.length - 1];
let d = 0,
r = 0,
c = -1;
while (scope[d % 2] > 0) {
for (let i = 0; i < scope[d % 2]; i++) {
r += dirs[d][0];
c += dirs[d][1];
res.push(inmatrix[r][c]);
}
scope[d % 2]--;
d = (d + 1) % 4;
}
return res;
}
​
try {
assert.equal(
spiraltraverse([
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
You're doing a wonderful job. Keep going!
If you had any problems with this tutorial, check out the main forum thread here.