LC-0286 Medium LeetCode Premium

286. Walls and Gates

This is a LeetCode premium problem — the official page requires a subscription. Read the full statement on leetcode.ca, a community mirror.

Difficulty: medium Acceptance: 63% Topics: Array, Breadth-First Search, Matrix

View full problem on leetcode.ca

Official page on LeetCode (premium)

The link at the top of the mirror page opens the solution — skip it if you want to solve this yourself.

leetcode.ca is an independent community site — we don't own or maintain it, and it isn't affiliated with LeetCode.

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(m * n)
# Space: O(g)

from collections import deque

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        INF = 2147483647
        q = deque([(i, j) for i, row in enumerate(rooms) for j, r in enumerate(row) if not r])
        while q:
            (i, j) = q.popleft()
            for I, J in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
                if 0 <= I < len(rooms) and 0 <= J < len(rooms[0]) and \
                   rooms[I][J] == INF:
                    rooms[I][J] = rooms[i][j] + 1
                    q.append((I, J))

Solution from kamyu104/LeetCode-Solutions · MIT