Coding Interview Questions | 01 Matrix

January 7th, 2024

Matrix 01 Problem Introduction:

This summary will talk about my solution to the 01 matrix problem as seen on leetcode here.

How do you solve the 01 Matrix Problem using Breadth-First-Search?

Solution:

type MatrixEntry = { row: number; col: number };

const updateMatrix = (mat: number[][]): number[][] => {
  const totalRows = mat.length;
  const totalCols = mat[0].length;
  const directions = [
    { row: 0, col: -1 },
    { row: 0, col: 1 },
    { row: -1, col: 0 },
    { row: 1, col: 0 },
  ];

  const distanceMatrix: number[][] = Array.from({ length: totalRows }, () =>
    Array(totalCols).fill(Infinity)
  );

  const queue: MatrixEntry[] = [];

  // Enqueue all cells with value 0, set their distance to 0
  for (let row = 0; row < totalRows; row++) {
    for (let col = 0; col < totalCols; col++) {
      if (mat[row][col] === 0) {
        queue.push({ row, col });
        distanceMatrix[row][col] = 0;
      }
    }
  }

  // Perform BFS from each cell with value 0
  while (queue.length > 0) {
    const { row, col } = queue.shift()!;

    for (const dir of directions) {
      const newRow = row + dir.row;
      const newCol = col + dir.col;

      if (
        newRow >= 0 &&
        newRow < totalRows &&
        newCol >= 0 &&
        newCol < totalCols
      ) {
        if (distanceMatrix[newRow][newCol] > distanceMatrix[row][col] + 1) {
          // If the new distance is smaller, update the distance and enqueue the cell
          distanceMatrix[newRow][newCol] = distanceMatrix[row][col] + 1;
          queue.push({ row: newRow, col: newCol });
        }
      }
    }
  }

  return distanceMatrix;
};

01 Matrix Solution Summary:

Below is a breakdown of the key aspects of the solution above:

1. Initialization: The algorithm initializes essential variables, including the matrix dimensions (totalRows and totalCols) and a set of directions for adjacent cells.
2. Distance Matrix Setup: It sets up a distanceMatrix to store the distance of each cell to the nearest 0, initially filled with infinity. Cells with value 0 are enqueued, and their distance is set to 0.
3. Breadth-First Search (BFS): The algorithm performs BFS starting from each cell with a value of 0. It explores adjacent cells, updating their distance if a shorter path is found, and enqueues them for further exploration.
4. Result: The distanceMatrix is returned, containing the distance of each cell to the nearest 0.

Complexities

1. Time Complexity: The time complexity is determined by the BFS traversal, making it O(m * n), where m is the number of rows and n is the number of columns in the matrix.
2. Space Complexity: The space complexity is O(m * n) due to the distanceMatrix and the queue used for BFS, where m is the number of rows and n is the number of columns in the matrix.