Coding Interview Questions | Spiral Matrix

February 2nd, 2024

Spiral Matrix Problem Introduction:

This summary will talk about my solution to the spiral matrix problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

Given an m x n matrix, return all elements of the matrix in spiral order.

How do you solve the Spiral Matrix Problem using depth-first search?

Solution:

// Directions are in spiral order: right -> down -> left -> up
const DIRECTIONS: { rowMove: number; colMove: number }[] = [
  { colMove: 1, rowMove: 0 },
  { colMove: 0, rowMove: 1 },
  { colMove: -1, rowMove: 0 },
  { colMove: 0, rowMove: -1 },
];

function spiralOrder(matrix: number[][]): number[] {
  const MAX_ROWS = matrix.length;
  // Guaranteed to have one row
  const MAX_COLS = matrix[0].length;
  const visited = Array.from({ length: matrix.length }, () =>
    matrix[0].map((_) => false)
  );

  const nodeStack = [{ row: 0, col: 0 }];
  const output = [];
  let currentDirectionIdx = 0;

  while (nodeStack.length > 0) {
    const { row, col } = nodeStack.pop()!;
    visited[row][col] = true;
    output.push(matrix[row][col]);

    const directionCountMap = new Map<number, number>();
    const firstDirectionIdx = currentDirectionIdx;
    directionCountMap.set(currentDirectionIdx, 1);

    while (directionCountMap.get(firstDirectionIdx)! < 2) {
      const { colMove, rowMove } = DIRECTIONS[currentDirectionIdx];
      const nextRow = row + rowMove;
      const nextCol = col + colMove;

      if (
        nextRow >= 0 &&
        nextRow < MAX_ROWS &&
        nextCol >= 0 &&
        nextCol < MAX_COLS &&
        !visited[nextRow][nextCol]
      ) {
        nodeStack.push({ col: nextCol, row: nextRow });
        break;
      } else {
        currentDirectionIdx = (currentDirectionIdx + 1) % 4;
        directionCountMap.set(
          currentDirectionIdx,
          directionCountMap.get(currentDirectionIdx)
            ? directionCountMap.get(currentDirectionIdx)! + 1
            : 1
        );
      }
    }
  }

  return output;
}

Spiral Order Matrix Solution Summary:

Below is a breakdown of the key aspects of the solution for the Spiral Order Matrix problem as seen above:

1. Directions Array: The algorithm defines a DIRECTIONS array representing the movements in spiral order: right, down, left, and up.

2. Matrix Dimensions: The algorithm determines the maximum number of rows and columns in the input matrix (MAX_ROWS and MAX_COLS).

3. Visited Array: It creates a visited array to keep track of visited elements in the matrix.

4. Node Stack: The algorithm initializes a stack (nodeStack) with the starting node and an empty output array.

5. Traversal: The algorithm traverses the matrix in a spiral order by popping nodes from the stack, marking them as visited, and adding them to the output array.

6. Direction Counting: It uses a directionCountMap to count how many times it attempts to move in a specific direction. If it fails to move in a direction, it updates the current direction.

7. Result: The final result is the output array containing elements of the matrix in spiral order.

Complexities:

1. Time Complexity: The time complexity is determined by the number of elements in the matrix, and the algorithm visits each element exactly once. It can be expressed as O(m * n), where m is the number of rows, and n is the number of columns.

2. Space Complexity: The space complexity is O(m * n) due to the visited array and the output array.