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 either0
or1
.- There is at least one
0
inmat
.
Потребление ресурсов¶
⏱ 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