Перейти к содержанию

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:

![https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg](https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg)

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

Example 2:

![https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg](https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg)

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