01 Matrix

🇷🇺 Название: Матрица 01
LeetCode: 01-matrix
Временная сложность: O(n*m)
Пространственная сложность: O(n*m)

Решение

from collections import deque  
from typing import List  


class Solution:  
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:  
        rows, cols = len(mat), len(mat[0])  
        queue = deque()  
        visited = [[False] * cols for _ in range(rows)]  

        for r in range(rows):  
            for c in range(cols):  
                if mat[r][c] == 0:  
                    queue.append((r, c))  
                    visited[r][c] = True  

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  

        while queue:  
            r, c = queue.popleft()  
            for dr, dc in directions:  
                nr, nc = r + dr, c + dc  
                if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:  
                    mat[nr][nc] = mat[r][c] + 1  
                    visited[nr][nc] = True  
                    queue.append((nr, nc))  

        return mat

🇺🇸 Условие

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

The distance between two cells sharing a common edge 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] ]

{
  "examples": [
    {
      "input": {
        "mat": [
          [0,0,0],
          [0,1,0],
          [0,0,0]
        ]
      },
      "output": [
        [0,0,0],
        [0,1,0],
        [0,0,0]
      ]
    },
    {
      "input": {
        "mat": [
          [0,0,0],
          [0,1,0],
          [1,1,1]
        ]
      },
      "output": [
        [0,0,0],
        [0,1,0],
        [1,2,1]
      ]
    }
  ]
}

Ограничения

• \(m \equiv mat.length\)
• \(n \equiv mat[i].length\)
• \(1 \leq m, n \leq 10^4\)
• \(1 \leq m * n \leq 10^4\)
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

Потребление ресурсов

⏱ Time complexity: O(n*m)

• Каждая ячейка обрабатывается один раз в BFS

Итог: O(n*m)

🧠 Space complexity: O(n*m)

• Очередь и visited массив — максимум по одной записи на ячейку

Итог: O(n*m)

medium array dynamic-programming breadth-first-search matrix

---

Metadata

• title_rus: Матрица 01
• difficulty: Medium
• leetcode_url: https://leetcode.com/problems/01-matrix/
• topics: ['Array', 'Dynamic Programming', 'Breadth-First Search', 'Matrix']
• time: O(n*m)
• space: O(n*m)
• grind75: True
• tags: ['Array', 'Breadth-First Search', 'Dynamic Programming', 'Matrix', 'Medium', 'problem']
• git_revision_date_localized: 5 июля 2025 г.
• git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_revision_date_localized_tag:
• git_revision_date_localized_raw_date: 5 июля 2025 г.
• git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_revision_date_localized_raw_iso_date: 2025-07-05
• git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_revision_date_localized_raw_timeago:
• git_revision_date_localized_raw_custom: 05. июля 2025
• git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_site_revision_date_localized_tag:
• git_site_revision_date_localized: 5 июля 2025 г.
• git_site_revision_date_localized_raw_date: 5 июля 2025 г.
• git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_site_revision_date_localized_raw_iso_date: 2025-07-05
• git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_site_revision_date_localized_raw_timeago:
• git_site_revision_date_localized_raw_custom: 05. июля 2025