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 in matrix[0][1], we encounter the green portion.
• Once we get to the 12 in matrix[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.

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, using O(1) space and O(n*m) time complexity, with all values between -1000000000 and 1000000000.
• 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, with colLower, colUpper, rowLower, and rowUpper 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 decrementing colUpper after each iteration.
• The algorithm to traverse an m * n matrix in spiral order has a linear time complexity and fixed space complexity of O(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],

That's all we've got! Let's move on to the next tutorial.

If you had any problems with this tutorial, check out the main forum thread here.