2812. Find the Safest Path in a Grid - Explanation

1. Multi Source BFS + Dijkstra's Algorithm

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

        def in_bounds(r, c):
            return min(r, c) >= 0 and max(r, c) < N

        def precompute():
            q = deque()
            min_dist = {}
            for r in range(N):
                for c in range(N):
                    if grid[r][c]:
                        q.append([r, c, 0])
                        min_dist[(r, c)] = 0
            while q:
                r, c, dist = q.popleft()
                nei = [[r+1, c], [r-1, c], [r, c+1], [r, c-1]]
                for r2, c2 in nei:
                    if in_bounds(r2, c2) and (r2, c2) not in min_dist:
                        min_dist[(r2, c2)] = dist + 1
                        q.append([r2, c2, dist + 1])
            return min_dist

        min_dist = precompute()
        maxHeap = [(-min_dist[(0, 0)], 0, 0)]  # (dist, r, c)
        visit = set()
        visit.add((0, 0))

        while maxHeap:
            dist, r, c = heapq.heappop(maxHeap)
            dist = -dist
            if (r, c) == (N-1, N-1):
                return dist
            nei = [[r+1, c], [r-1, c], [r, c+1], [r, c-1]]
            for r2, c2 in nei:
                if in_bounds(r2, c2) and (r2, c2) not in visit:
                    visit.add((r2, c2))
                    dist2 = min(dist, min_dist[(r2, c2)])
                    heapq.heappush(maxHeap, (-dist2, r2, c2))

Time & Space Complexity

Time complexity: $O(n ^ 2 \log n)$
Space complexity: $O(n ^ 2)$

2. Multi Source BFS + Dijkstra's Algorithm (Overwriting the Input)

class Solution:
    def maximumSafenessFactor(self, grid):
        N = len(grid)
        minDist = grid
        directions = [0, 1, 0, -1, 0]

        q = deque()
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    q.append(r * N + c)
                    minDist[r][c] = 0
                else:
                    minDist[r][c] = -1

        while q:
            node = q.popleft()
            r, c = divmod(node, N)
            for i in range(4):
                r2, c2 = r + directions[i], c + directions[i + 1]
                if 0 <= r2 < N and 0 <= c2 < N and minDist[r2][c2] == -1:
                    minDist[r2][c2] = minDist[r][c] + 1
                    q.append(r2 * N + c2)

        maxHeap = [(-minDist[0][0], 0)]
        safeFactor = [0] * (N * N)
        safeFactor[0] = minDist[0][0]

        while maxHeap:
            dist, node = heapq.heappop(maxHeap)
            dist = -dist
            r, c = divmod(node, N)
            if r == N - 1 and c == N - 1:
                return dist
            if safeFactor[node] > dist:
                continue

            for i in range(4):
                r2, c2 = r + directions[i], c + directions[i + 1]
                node2 = r2 * N + c2
                if 0 <= r2 < N and 0 <= c2 < N:
                    dist2 = min(dist, minDist[r2][c2])
                    if dist2 > safeFactor[node2]:
                        safeFactor[node2] = dist2
                        heapq.heappush(maxHeap, (-dist2, node2))

        return 0

Time & Space Complexity

Time complexity: $O(n ^ 2 \log n)$
Space complexity: $O(n ^ 2)$

3. Multi Source BFS + Binary Search

class Solution:
    def maximumSafenessFactor(self, grid):
        N = len(grid)
        minDist = grid
        directions = [0, 1, 0, -1, 0]

        q = deque()
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    q.append(r * N + c)
                    minDist[r][c] = 0
                else:
                    minDist[r][c] = -1

        while q:
            node = q.popleft()
            r, c = divmod(node, N)
            for i in range(4):
                r2, c2 = r + directions[i], c + directions[i + 1]
                if 0 <= r2 < N and 0 <= c2 < N and minDist[r2][c2] == -1:
                    minDist[r2][c2] = minDist[r][c] + 1
                    q.append(r2 * N + c2)

        def canReach(threshold):
            q = deque([0])
            visited = [False] * (N * N)
            visited[0] = True

            while q:
                node = q.popleft()
                r, c = divmod(node, N)
                if r == N - 1 and c == N - 1:
                    return True

                for i in range(4):
                    r2, c2 = r + directions[i], c + directions[i + 1]
                    node2 = r2 * N + c2
                    if (0 <= r2 < N and 0 <= c2 < N and not visited[node2] and
                        minDist[r2][c2] >= threshold
                    ):
                        visited[node2] = True
                        q.append(node2)

            return False

        l, r = 0, min(minDist[0][0], minDist[N - 1][N - 1])
        while l <= r:
            mid = (l + r) // 2
            if canReach(mid):
                l = mid + 1
            else:
                r = mid - 1

        return l - 1

Time & Space Complexity

Time complexity: $O(n ^ 2 \log n)$
Space complexity: $O(n ^ 2)$

4. Breadth First Search (0-1 BFS)

class Solution:
    def maximumSafenessFactor(self, grid):
        N = len(grid)
        minDist = grid
        directions = [0, 1, 0, -1, 0]

        q = deque()
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    q.append(r * N + c)
                    minDist[r][c] = 0
                else:
                    minDist[r][c] = -1

        while q:
            node = q.popleft()
            r, c = divmod(node, N)
            for i in range(4):
                r2, c2 = r + directions[i], c + directions[i + 1]
                if 0 <= r2 < N and 0 <= c2 < N and minDist[r2][c2] == -1:
                    minDist[r2][c2] = minDist[r][c] + 1
                    q.append(r2 * N + c2)

        safeFactor = [-1] * (N * N)
        res = safeFactor[0] = min(minDist[N - 1][N - 1], minDist[0][0])
        q.append(0)

        while q:
            node = q.popleft()
            r, c = divmod(node, N)
            res = min(res, safeFactor[node])
            if r == N - 1 and c == N - 1:
                break

            for i in range(4):
                r2, c2 = r + directions[i], c + directions[i + 1]
                node2 = r2 * N + c2
                if 0 <= r2 < N and 0 <= c2 < N and safeFactor[node2] == -1:
                    safeFactor[node2] = min(safeFactor[node], minDist[r2][c2])
                    if safeFactor[node2] < res:
                        q.append(node2)
                    else:
                        q.appendleft(node2)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$