Leetcode 1117 Solution

This article provides solution to leetcode question 1117 (as-far-from-land-as-possible)
Categories:
Tags:
Access this page by simply typing in "lcs 1117" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/as-far-from-land-as-possible

Solution

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)

        q = collections.deque()

        for i in range(n):
            for j in range(n):
                if grid[i][j]:
                    q.append((i, j))

        step = 1
        while q:
            s = len(q)

            for _ in range(s):
                i, j = q.popleft()

                neighs = [
                    (i - 1, j),
                    (i + 1, j),
                    (i, j - 1),
                    (i, j + 1),
                ]

                for neigh in neighs:
                    if not 0 <= neigh[0] < n:
                        continue
                    if not 0 <= neigh[1] < n:
                        continue

                    if grid[neigh[0]][neigh[1]]:
                        continue

                    grid[neigh[0]][neigh[1]] = step + 1
                    q.append((neigh[0], neigh[1]))

            step += 1

        return step - 2 if step - 2 > 0 else -1