01 Matrix

---

01 Matrix: Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

---

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

---

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10^4
• 1 <= m * n <= 10^4
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

---

Try this Problem on your own or check similar problems:

1. Difference Between Ones and Zeros in Row and Column

Solution:

Java

class Solution {
  int[][] directions  = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};
  public int[][] updateMatrix(int[][] mat) {
      int m = mat.length, n = mat[0].length;

      for(int i = 0; i < m; ++i){
          for(int j = 0; j < n; ++j){
              if(mat[i][j] == 1) mat[i][j] = -1;
          }
      }

      for(int i = 0; i < m; ++i){
          for(int j = 0; j < n; ++j){
              putTheDistance(mat, i, j);
          }

          for(int j = n - 1; j >= 0; --j){
              putTheDistance(mat, i, j);
          }
      }

      for(int i = m - 1; i >= 0; --i){
          for(int j = 0; j < n; ++j){
              putTheDistance(mat, i, j);
          }

          for(int j = n - 1; j >= 0; --j){
              putTheDistance(mat, i, j);
          }
      }

      return mat;
  }

  private void putTheDistance(int[][] mat, int row, int col){
      if(mat[row][col] == 0) return;
      int minDistance = mat.length + mat[0].length + 1;
      for(int[] d: directions){
          int newRow = row + d[0];
          int newCol = col + d[1];
          if(newRow < 0 || newRow >= mat.length || newCol < 0 || newCol >= mat[0].length || mat[newRow][newCol] == -1) continue;
          minDistance = Math.min(mat[newRow][newCol] + 1, minDistance);
      }
      mat[row][col] = mat[row][col] == -1 ? minDistance : Math.min(mat[row][col], minDistance);
  }
}

JavaScript

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
const directions = [
  [1, 0],
  [0, 1],
  [-1, 0],
  [0, -1],
];
var updateMatrix = function (mat) {
  const m = mat.length;
  const n = mat[0].length;

  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (mat[i][j] === 1) {
        mat[i][j] = -1;
      }
    }
  }

  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      putTheDistance(mat, i, j);
    }

    for (let j = n - 1; j >= 0; --j) {
      putTheDistance(mat, i, j);
    }
  }

  for (let i = m - 1; i >= 0; --i) {
    for (let j = 0; j < n; ++j) {
      putTheDistance(mat, i, j);
    }

    for (let j = n - 1; j >= 0; --j) {
      putTheDistance(mat, i, j);
    }
  }

  return mat;
};

function putTheDistance(mat, row, col) {
  if (mat[row][col] === 0) return;
  let minDistance = mat.length + mat[0].length + 1;
  for (const [dx, dy] of directions) {
    const newRow = row + dx;
    const newCol = col + dy;
    if (
      newRow < 0 ||
      newRow >= mat.length ||
      newCol < 0 ||
      newCol >= mat[0].length ||
      mat[newRow][newCol] === -1
    )
      continue;
    minDistance = Math.min(mat[newRow][newCol] + 1, minDistance);
  }
  mat[row][col] =
    mat[row][col] === -1 ? minDistance : Math.min(mat[row][col], minDistance);
}

Python

class Solution:
    directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    mat[i][j] = -1

        for i in range(m):
            for j in range(n):
                self.putTheDistance(mat, i, j)

            for j in range(n - 1, -1, -1):
                self.putTheDistance(mat, i, j)

        for i in range(m - 1, -1, -1):
            for j in range(n):
                self.putTheDistance(mat, i, j)

            for j in range(n - 1, -1, -1):
                self.putTheDistance(mat, i, j)

        return mat

    def putTheDistance(self, mat: List[List[int]], row: int, col: int) -> None:
        if mat[row][col] == 0:
            return
        minDistance = len(mat) + len(mat[0]) + 1
        for d in self.directions:
            newRow = row + d[0]
            newCol = col + d[1]
            if newRow < 0 or newRow >= len(mat) or newCol < 0 or newCol >= len(mat[0]) or mat[newRow][newCol] == -1:
                continue
            minDistance = min(mat[newRow][newCol] + 1, minDistance)
        mat[row][col] = minDistance if mat[row][col] == -1 else min(mat[row][col], minDistance)

C++

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    mat[i][j] = -1;
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                putTheDistance(mat, i, j);
            }

            for (int j = n - 1; j >= 0; --j) {
                putTheDistance(mat, i, j);
            }
        }

        for (int i = m - 1; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                putTheDistance(mat, i, j);
            }

            for (int j = n - 1; j >= 0; --j) {
                putTheDistance(mat, i, j);
            }
        }

        return mat;
    }

private:
    std::vector<std::vector<int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    void putTheDistance(std::vector<std::vector<int>>& mat, int row, int col) {
        if (mat[row][col] == 0) {
            return;
        }
        int minDistance = mat.size() + mat[0].size() + 1;
        for (const auto& d : directions) {
            int newRow = row + d[0];
            int newCol = col + d[1];
            if (newRow < 0 || newRow >= mat.size() || newCol < 0 || newCol >= mat[0].size() || mat[newRow][newCol] == -1) {
                continue;
            }
            minDistance = std::min(mat[newRow][newCol] + 1, minDistance);
        }
        mat[row][col] = mat[row][col] == -1 ? minDistance : std::min(mat[row][col], minDistance);
    }
};

---

Time/Space Complexity:

• Time Complexity: O(mn)
• Space Complexity: O(1)

---

Explanation:

We could perform BFS breadth first search to calculate the distance from the zeroes. We can place the coordinates of all zeroes as initial candidates in the queue and use the directions to check every neighbor of the initial candidate. We also check if can improve neighbors distance by using current set of candidates. Of course, when we cover all neighbors of zeroes, we move to the next set of candidates with distance 2 (from initial set of candidates) and so on (like the level traversal of binary tree, we move further and further from the initial set of candidates, in tree that would be the root). Also note that we can reuse the initial input matrix for the distance storing purposes if we mark not-calculated fields with special numbers, since distances are positive numbers, we can use any negative number to mark field we haven't calculated the distance for. Time and space complexity are linear to the size of matrix O(mn).

Java

class Solution {
  int[][] directions  = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};
  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] == 1) mat[i][j] = -1;
              else q.add(new int[]{i, j});
          }
      }

      while(!q.isEmpty()){
          int[] current = q.poll();
          for(int[] d: directions){
              int newRow = current[0] + d[0];
              int newCol = current[1] + d[1];
              if(newRow < 0 || newRow >= mat.length || newCol < 0 || newCol >= mat[0].length) continue;
              if(mat[newRow][newCol] == -1 || mat[newRow][newCol] > mat[current[0]][current[1]] + 1){
                  mat[newRow][newCol] = mat[current[0]][current[1]] + 1;
                  q.add(new int[]{newRow, newCol});
              }
          }
      }

      return mat;
  }
}

JavaScript

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function (mat) {
  const directions = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ];
  const m = mat.length;
  const n = mat[0].length;
  const queue = [];

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (mat[i][j] === 1) {
        mat[i][j] = -1;
      } else {
        queue.push([i, j]);
      }
    }
  }

  while (queue.length > 0) {
    const current = queue.shift();
    for (const d of directions) {
      const newRow = current[0] + d[0];
      const newCol = current[1] + d[1];
      if (
        newRow < 0 ||
        newRow >= mat.length ||
        newCol < 0 ||
        newCol >= mat[0].length
      ) {
        continue;
      }
      if (
        mat[newRow][newCol] === -1 ||
        mat[newRow][newCol] > mat[current[0]][current[1]] + 1
      ) {
        mat[newRow][newCol] = mat[current[0]][current[1]] + 1;
        queue.push([newRow, newCol]);
      }
    }
  }

  return mat;
};

Python

class Solution:
    directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    m = len(mat)
    n = len(mat[0])
    queue = deque()

    for i in range(m):
        for j in range(n):
            if mat[i][j] == 1:
                mat[i][j] = -1
            else:
                queue.append((i, j))

    while queue:
        current = queue.popleft()
        for d in directions:
            newRow = current[0] + d[0]
            newCol = current[1] + d[1]
            if (
                newRow < 0
                or newRow >= len(mat)
                or newCol < 0
                or newCol >= len(mat[0])
            ):
                continue
            if (
                mat[newRow][newCol] == -1
                or mat[newRow][newCol] > mat[current[0]][current[1]] + 1
            ):
                mat[newRow][newCol] = mat[current[0]][current[1]] + 1
                queue.append((newRow, newCol))

    return mat

C++

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        std::vector<std::vector<int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int m = mat.size();
        int n = mat[0].size();
        std::queue<std::pair<int, int>> q;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    mat[i][j] = -1;
                } else {
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            auto current = q.front();
            q.pop();
            for (const auto& d : directions) {
                int newRow = current.first + d[0];
                int newCol = current.second + d[1];
                if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n) {
                    continue;
                }
                if (mat[newRow][newCol] == -1 ||
                    mat[newRow][newCol] > mat[current.first][current.second] + 1) {
                    mat[newRow][newCol] = mat[current.first][current.second] + 1;
                    q.push({newRow, newCol});
                }
            }
        }

        return mat;
    }
};

But we can also note that distance of certain field can be only updated from 4 sides (up, down, left, right) so the distance of mat[i][j] is determined by the minimum distance of its neighbors assuming mat[i][j] != 0 (since the distance is already 0), so if we traverse each row from up to down and left and right, and then from down to up and from left to right we would have calculated the best distance for each field since we test the best distance from all 4 sides/neighbors. This time we're not using any additional space. Also note that we used minDistance = mat.length + mat[0].length + 1; to initially mark it as the maximum distance (before we try to minimize it) a field in matrix can have. It represents the sum of columns and rows lengths (you can imagine two ends of the matrix, go first to the end of the first row, and then go from there down, through the last column).