542. 01 Matrix

Approach

Using BFS with source as all cells containing 0s and updating the distance values until all paths are exhausted.

Code

public int[][] updateMatrix(int[][] mat) {
  int m = mat.length, n = mat[0].length;
  Queue<int[]> q = new LinkedList<>();

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (mat[i][j] == 0) {
        q.add(new int[] { i, j });
      } else {
        mat[i][j] = Integer.MAX_VALUE;
      }
    }
  }

  int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

  while (!q.isEmpty()) {
    int[] head = q.remove();
    int i = head[0];
    int j = head[1];

    for (int k = 0; k < dirs.length; k++) {
      int x = i + dirs[k][0];
      int y = j + dirs[k][1];

      if (x < 0 || x == m || y < 0 || y == n) continue;
      if (mat[x][y] <= mat[i][j] + 1) continue;

      mat[x][y] = mat[i][j] + 1;
      q.add(new int[] { x, y });
    }
  }

  return mat;
}

Time complexity	Space complexity
\(\mathcal{O}(m*n)\)	\(\mathcal{O}(m*n)\)