Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 286 with 17 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 286 # by problem number
lcpy gen -s walls_and_gates # by problem name
m × n 2D grid initialized with these three possible values:
-1 - A wall or obstacle that can not be traversed.0 - A gate.INF - Infinity an empty room. We use the value 2^31 - 1 = 2147483647 to represent INF.INF.
Follow up: Can you solve it in-place and in O(m × n) time complexity?
Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
Input: rooms = [[0,-1],[2147483647,2147483647]]
Output: [[0,-1],[1,2]]
m == rooms.lengthn == rooms[i].length1 <= m, n <= 100rooms[i][j] is one of -1, 0, or 2147483647.from collections import deque
class Solution:
# Time: O(m * n)
# Space: O(m * n)
def walls_and_gates(self, rooms: list[list[int]]) -> None:
if not rooms or not rooms[0]:
return
rows, cols = len(rooms), len(rooms[0])
queue: deque[tuple[int, int]] = deque()
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
queue.append((r, c))
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 rooms[nr][nc] == 2147483647:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
| Time | Space |
|---|---|
| O(m * n) | O(m * n) |