2812. Find the Safest Path in a Grid
Asked at Uber
Difficulty
Medium
Time
O(n^2 log n)
Space
O(n^2)
Pattern
Array
Companies
1
Problem
You are given an n x n grid. A cell with value 1 holds a thief, and a cell with value 0 is empty. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1). In one move you may step to a cell that shares an edge with your current cell (up, down, left, right). You are allowed to walk on thief cells.
The safeness factor of a path is the smallest Manhattan distance between any cell on that path and any thief in the whole grid. In other words, look at every cell you visit, measure its distance to the closest thief, and take the minimum of those numbers.
Return the largest safeness factor you can get over all paths from the start to the goal.
What the safeness factor measures
Constraints
- ●
1 <= grid.length == n <= 400 - ●
grid[i].length == n - ●
grid[i][j] is either 0 or 1 - ●
There is at least one thief in the grid
Examples
grid = [[1,0,0],[0,0,0],[0,0,1]]0grid = [[0,0,1],[0,0,0],[0,0,0]]2grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]2Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Uber | Medium | View all Uber questions → |
How to Think About It
Brute force: enumerate all paths (exponential) and compute safety for each — infeasible.
Compute Manhattan distance from every cell to nearest thief using multi-source BFS.
Binary search on the safety threshold: for a given value mid, check if a valid path exists using only cells with distance >= mid.
Alternatively use a max-heap (priority queue) starting from (0,0), always expanding the cell with highest safety.
Both approaches are O(n^2 log n) — binary search uses BFS/DFS per check, heap approach is single-pass with heap ops.
Optimal Approach
First, run a multi-source BFS from all thief cells to compute the minimum Manhattan distance from every cell to the nearest thief. Then binary search on the safety value: for each candidate mid, check if a path exists from (0,0) to (n-1,n-1) using only cells whose distance is at least mid. The check is a simple BFS/DFS. Return the largest mid that yields a valid path. Time complexity is O(n^2 log n).
Distance map, then binary search
What Trips People Up in Real Interviews
Clarify what Manhattan distance means — |r1-r2| + |c1-c2|.
Confirm the grid is square (n x n) and values are non-negative.
Edge case: grid[0][0] has a thief — safety of any path is 0.
Discuss trade-offs between binary search + BFS vs. heap-based approach.
Be careful with the binary search bounds: low=0, high=2*n.
Solution Code
O(n^2 log n) timedef maximumSafenessFactor(grid):
from collections import deque
n = len(grid)
dist = [[-1]*n for _ in range(n)]
q = deque()
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
dist[i][j] = 0
q.append((i, j))
while q:
r, c = q.popleft()
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
def canReach(threshold):
if dist[0][0] < threshold:
return False
visited = [[False]*n for _ in range(n)]
stack = [(0, 0)]
visited[0][0] = True
while stack:
r, c = stack.pop()
if r == n-1 and c == n-1:
return True
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and dist[nr][nc] >= threshold:
visited[nr][nc] = True
stack.append((nr, nc))
return False
lo, hi = 0, 2 * n
while lo < hi:
mid = (lo + hi + 1) // 2
if canReach(mid):
lo = mid
else:
hi = mid - 1
return loFrequently Asked Questions
What is the Find the Safest Path in a Grid problem?
You are given a 0-indexed 2D grid grid where grid[i][j] represents the number of thieves at that cell. The safety of a path from (0,0) to (n-1,n-1) is the minimum Manhattan distance from any cell on the path to any thief. Return the maximum possible safety value of any path from top-left to bottom-right.
How do you solve Find the Safest Path in a Grid?
The optimal approach runs in O(n^2 log n) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Find the Safest Path in a Grid?
Find the Safest Path in a Grid is asked at Uber. It is a medium difficulty problem.
What are common mistakes on Find the Safest Path in a Grid?
- Clarify what Manhattan distance means — |r1-r2| + |c1-c2|.
- Confirm the grid is square (n x n) and values are non-negative.
- Edge case: grid[0][0] has a thief — safety of any path is 0.
- Discuss trade-offs between binary search + BFS vs. heap-based approach.
- Be careful with the binary search bounds: low=0, high=2*n.