Spiral Traversal

Given a 2D matrix of numbers, return a spiral traversal of the matrix in the clockwise direction.

Iterative solution

In the iterative solution, we are going to traverse the matrix Row wise and Column wise, covering all the elements.

We declare 4 pointers

  1. startRow - 0
  2. startCol - 0
  3. endRow - arr.length - 1
  4. endCol - arr[0].length - 1

These pointers denote the starting and ending of columns and rows in the matrix. Moving these pointers and storing the results in an array will be our primary approach.

  1. While startRow <= endRow && startCol <= endCol, We iterate over the first row, then the last column, then the last row, then the first column. This will ensure that we cover all the boundries of the matrix and push it into the array in a clockwise direction.
  2. For the Top Row, Iterate from startCol to endCol - push the row elements in the array i.e. arr[startRow][i].
  3. For the Right Column, Iterate from the startRow to endRow - push the column elements in the array i.e. arr[i][endCol].
  4. For the Bottom Row, Iterate from the endCol to startCol - Push the row elements in the array. i.e. arr[endRow][i]
  5. For the Left Column, Iterate from endRow to startRow - Push the column elements in the array. i.e. arr[i][startCol]

At every step, we decrement end indices and increment start indices because after covering the boundries of the matrix, we need to get one level deeper to print out the remaining elements.

Return the results array after the while loop breaks.

Time Complexity

  • O(n^2) - Because we have to iterate over all the elements (while loop and for loop)

Recursive Approach

This approach is pretty much the same as the Iterative Approach in terms of the logic, the only thing that differes is how we step into the nested levels of the matrix.

We create a helper function that has the start and the end indices of Rows and columns.

  spiralTraversalRecursiveHelper(
    arr,
    startRow,
    endRow,
    startCol,
    endCol,
    result
  );

The base condition of the recursion will be if (startRow > endRow || startCol > endCol). This is where we need to return.

We declare 4 pointers

  1. startRow - 0
  2. startCol - 0
  3. endRow - arr.length - 1
  4. endCol - arr[0].length - 1

These pointers denote the starting and ending of columns and rows in the matrix. Moving these pointers and storing the results in an array will be our primary approach.

  1. We iterate over the first row, then the last column, then the last row, then the first column. This will ensure that we cover all the boundries of the matrix and push it into the array in a clockwise direction.
  2. For the Top Row, Iterate from startCol to endCol - push the row elements in the array i.e. arr[startRow][i].
  3. For the Right Column, Iterate from the startRow to endRow - push the column elements in the array i.e. arr[i][endCol].
  4. For the Bottom Row, Iterate from the endCol to startCol - Push the row elements in the array. i.e. arr[endRow][i]
  5. For the Left Column, Iterate from endRow to startRow - Push the column elements in the array. i.e. arr[i][startCol].
  6. Once we reach at the end of the function, we recursively call the helper function to get one level deeper into the matrix.

At every step, we decrement end indices and increment start indices because after covering the boundries of the matrix, we need to get one level deeper to print out the remaining elements.

Solve Spiral Traversal on Algochurn

Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn