We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Safest Path in a Grid

Number: 2914

Difficulty: Medium

Paid? No

Companies: Google, IMC, Amazon

Problem Description

Given an n x n grid where cells contain either 0 (empty) or 1 (a thief), you must find a path from cell (0, 0) to (n - 1, n - 1). The safeness factor of a path is defined as the minimum Manhattan distance from any cell in the path to any thief in the grid. The goal is to maximize this safeness factor over all possible valid paths (moving up, down, left, or right).

Key Insights

  • Compute for each cell the Manhattan distance to its nearest thief. This is efficiently done via multi-source BFS starting from every cell containing a thief.
  • With precomputed distances, the problem becomes one of finding a path from the start to the end such that every visited cell has a distance (safeness factor) at least X.
  • Use binary search (or a Dijkstra-style max-min path algorithm) to find the maximum possible X such that a valid path exists.
  • During the binary search, perform a BFS or DFS from (0, 0) using only cells whose distance from a thief is >= candidate value X.

Space and Time Complexity

Time Complexity: O(n^2 log(n))
Space Complexity: O(n^2)

Solution

  1. Use multi-source BFS to compute a distance matrix (dist) where dist[r][c] is the Manhattan distance from cell (r, c) to the nearest thief.
  2. Perform a binary search on the possible safeness factor X. For each candidate X:
    • Check if (0, 0) itself has distance >= X. If yes, do a BFS/DFS from (0,0) considering only cells with distance >= X.
    • If you can reach (n - 1, n - 1), candidate X is feasible.
  3. The binary search finds the maximum X for which a valid path exists.

Data Structures and Techniques:

  • Queue for multi-source BFS for computing distance.
  • Another queue (or stack) for the connectivity check during binary search.
  • Binary search to efficiently pinpoint the maximum safeness factor.

Important considerations:

  • The multi-source BFS starts with all thief cells; their initial distance is 0.
  • During connectivity check, boundary conditions and proper marking of visited cells are essential.
  • The grid size (up to 400 x 400) requires efficient O(n^2) traversals and careful management of recursion/iteration.

Code Solutions

from collections import deque

def safestPath(grid):
    n = len(grid)
    # Directions for adjacent moves (up, down, left, right)
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    # Step 1: Multi-source BFS to calculate minimum distance to a thief for each cell.
    dist = [[-1] * n for _ in range(n)]
    queue = deque()
    
    # Initialize queue with all thief positions (distance = 0)
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                dist[i][j] = 0
                queue.append((i, j))
    
    # Perform BFS
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                queue.append((nx, ny))
    
    # Function to check if a valid path exists for a given safeness threshold.
    def canReach(threshold):
        if dist[0][0] < threshold:
            return False
        visited = [[False] * n for _ in range(n)]
        q = deque()
        q.append((0,0))
        visited[0][0] = True
        while q:
            x, y = q.popleft()
            if x == n - 1 and y == n - 1:
                return True
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and dist[nx][ny] >= threshold:
                    visited[nx][ny] = True
                    q.append((nx, ny))
        return False
    
    # Step 2: Binary search for the maximum safeness factor.
    lo, hi = 0, max(max(row) for row in dist)
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if canReach(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

# Example usage:
grid1 = [[1,0,0],[0,0,0],[0,0,1]]
print(safestPath(grid1))  # Output: 0
← Back to All Questions