Leetcode # 542. 01 Matrix

https://leetcode.com/problems/01-matrix/

⭐️ Solution: Breadth-First Serch

Time Complexity: O(r * c)
Space Complexity: O(1) ※ 不計算為了 output 所使用的 memory

class Solution:
  def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
    dist = [[None] * len(row) for row in mat]
    queue = collections.deque()
    for i, row in enumerate(mat):
      for j, cell in enumerate(row):
        if cell == 0:
          dist[i][j] = 0
          queue.append((i, j))
      
    while queue:
      i, j = queue.popleft()
      dis = dist[i][j] + 1
      for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < len(mat) and 0 <= nj < len(mat[0]):
          if dist[ni][nj] is None:
            dist[ni][nj] = dis
            queue.append((ni, nj))
            
    return dist

Solution: Dynamic Programming

先由左至右、由上至下計算距離
再由右至左、由下至上計算距離
最後取兩者距離小者

Time Complexity: O(2 * (r * c)) = O(r * c)
Space Complexity: O(1) ※ 不計算為了 output 所使用的 memory

class Solution:
  def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
    dist = [ [float("inf") for cell in row] for row in mat]
    for i in range(len(mat)):
      for j in range(len(mat[0])):
        if mat[i][j] == 0:
          dist[i][j] = 0
        else:
          if i > 0:
            dist[i][j] = dist[i - 1][j] + 1
          if j > 0:
            dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)
            
    for i in range(len(mat) - 1, -1, -1):
      for j in range(len(mat[0]) - 1, -1, -1):
        if i < len(mat) - 1:
          dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
        if j < len(mat[0]) - 1:
          dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)
            
    return dist

Last Updated on 2023/08/17 by A1go