Skip to main content
Talentd

Find the Safest Path in a Grid - Solution & Explanation

MediumArrayBinary SearchBreadth-First SearchUnion Find28 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents:

  • A cell containing a thief if grid[r][c] = 1
  • An empty cell if grid[r][c] = 0

You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves.

The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid.

Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1).

An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists.

The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val.

 

Example 1:

Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
Output: 0
Explanation: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).

Example 2:

Input: grid = [[0,0,1],[0,0,0],[0,0,0]]
Output: 2
Explanation: The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2.
It can be shown that there are no other paths with a higher safeness factor.

Example 3:

Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
Output: 2
Explanation: The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 3) is cell (1, 2). The distance between them is | 0 - 1 | + | 3 - 2 | = 2.
- The closest cell of the path to the thief at cell (3, 0) is cell (3, 2). The distance between them is | 3 - 3 | + | 0 - 2 | = 2.
It can be shown that there are no other paths with a higher safeness factor.

 

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.

Approach Overview

Problem Overview: You are given an n x n grid where cells containing 1 represent thieves. The goal is to travel from the top‑left cell to the bottom‑right cell while maximizing the minimum distance to any thief along the path. The safety of a path equals the smallest distance from any cell on that path to the nearest thief.

Approach 1: BFS with Distance Preprocessing (Multi‑Source BFS + Search) (Time: O(n² log n), Space: O(n²))

The key observation: instead of evaluating safety during traversal, first compute how safe every cell is. Run a multi‑source Breadth‑First Search starting from all thief cells simultaneously. This fills a matrix where dist[r][c] stores the shortest distance to the nearest thief. Once this preprocessing is done, the task becomes finding a path that maximizes the minimum value in dist.

To achieve that, perform a search on the answer. Use binary search on the possible safeness factor. For a candidate value k, run BFS from (0,0) and only step into cells whose dist value is at least k. If you can reach (n‑1,n‑1), that safeness level is feasible. Binary search finds the maximum valid value.

This approach separates the problem into two clean phases: computing distances with multi‑source BFS and validating paths with BFS. It is efficient because each grid cell is processed a constant number of times, and the binary search range is limited by the grid size.

Approach 2: Bidirectional BFS on the Safety Graph (Time: O(n²), Space: O(n²))

Another perspective treats the grid as a graph where each cell has a safety score from the preprocessing step. Instead of exploring from only the start, run BFS simultaneously from both the start and the destination. Each frontier expands through cells that satisfy the minimum safety constraint, and the search stops when the two frontiers meet.

Bidirectional BFS reduces the explored state space compared to a single-direction traversal because both ends converge toward the middle. This often improves practical performance on large grids where a single BFS would visit many unnecessary cells.

The preprocessing phase remains identical: compute the nearest‑thief distance for every cell using multi‑source BFS. After that, the bidirectional search checks connectivity under a chosen safety threshold while expanding from both sides.

Recommended for interviews: The multi‑source BFS + binary search solution is the one most interviewers expect. It demonstrates strong understanding of matrix traversal, BFS layering, and transforming a max‑min path problem into a monotonic search. Mentioning brute reasoning (checking paths directly) shows problem exploration, but implementing the BFS distance preprocessing with binary search shows the algorithmic insight interviewers look for.

Approach 1: BFS with Distance Preprocessing

This approach involves using Breadth-First Search (BFS) to precompute the minimum Manhattan distance from each cell to any thief in the grid, and then using this information to find the maximum safeness factor for reaching the bottom-right corner.

This C solution first performs a BFS from all thief positions to calculate the distance from each cell to the nearest thief. Then, it uses Dijkstra-like processing to find the maximum safeness from the top-left corner to the bottom-right corner.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n2 log n), where n is the grid size, due to the Dijkstra-like process.
Space Complexity: O(n2) for storing distances and safeness factors.

Try this approach in the editor →

Approach 2: Bidirectional BFS

This approach considers processing from both the starting and ending points in a bidirectional BFS style, potentially meeting in the middle for optimized distance calculations and safeness factor determination.

The C solution processes the grid using bidirectional BFS starting from both the top-left corner and the bottom-right corner simultaneously, aiming to explore overlapping paths and maximize their safeness factor.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n2) due to simultaneous BFS processing.
Space Complexity: O(n2) as distances from both ends are computed.

Try this approach in the editor →

Approach 3: BFS + Sorting + Union-Find

We can first find out the positions of all thieves, and then start multi-source BFS from these positions to get the shortest distance from each position to the thieves. Then sort in descending order according to the distance, and add each position to the union-find set one by one. If the start and end points are in the same connected component, the current distance is the answer.

The time complexity is O(n^2 times log n), and the space complexity O(n^2). Where n is the size of the grid.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Default Approach

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
BFS with Distance Preprocessing

Time Complexity: O(n2 log n), where n is the grid size, due to the Dijkstra-like process.
Space Complexity: O(n2) for storing distances and safeness factors.

Bidirectional BFS

Time Complexity: O(n2) due to simultaneous BFS processing.
Space Complexity: O(n2) as distances from both ends are computed.

BFS + Sorting + Union-Find—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with Distance Preprocessing + Binary SearchO(n² log n)O(n²)General solution for interview settings. Clean separation between computing safety distances and validating paths.
Bidirectional BFS with Safety ConstraintsO(n²)O(n²)Useful when reducing search space matters; explores from both start and destination simultaneously.

Video Solution

Find the Safest Path in a Grid - Leetcode 2812 - Python • NeetCodeIO • 22,682 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Safest Path in a Grid easy or hard?
The problem is rated Medium on LeetCode. The challenge comes from recognizing that you must first compute distances to thieves using multi-source BFS and then transform the task into a maximum-minimum path search using binary search or graph traversal.
How to solve Find the Safest Path in a Grid in O(n²)?
First compute the distance from each cell to the nearest thief using multi-source BFS. Then treat the grid as a graph with safety values and perform a constrained traversal such as bidirectional BFS or a priority-based search to maximize the minimum distance along the path. With efficient pruning, traversal processes each cell roughly once.
What is the best approach for Find the Safest Path in a Grid?
The most effective approach uses multi-source BFS to compute the distance from every cell to the nearest thief, followed by binary search on the safeness factor. For each candidate value, a BFS checks if a path exists using only cells whose distance is at least that value. This produces an O(n² log n) time complexity with O(n²) space.
Is Find the Safest Path in a Grid asked at Google/Amazon/Meta?
Grid traversal and multi-source BFS problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine BFS with binary search or priority queues are especially common because they test graph reasoning and optimization skills.
What data structure is used in Find the Safest Path in a Grid?
The solution primarily uses queues for BFS traversal, a matrix to store nearest-thief distances, and sometimes binary search over the answer space. In some implementations, union-find or priority queues can also be used to process cells in decreasing safety order.
What is the time complexity of Find the Safest Path in a Grid?
The common optimized solution runs in O(n² log n) time. Multi-source BFS to compute distances takes O(n²), and each binary search step runs a BFS that may visit all cells. Space complexity is O(n²) for the distance matrix and BFS queues.
Find the Safest Path in a Grid Python or Java solution approach
Python and Java implementations follow the same pattern: run multi-source BFS from all thief cells to fill a distance grid, then binary search the safeness factor while validating reachability with BFS. Both languages achieve O(n² log n) time and O(n²) space.

Ready to solve this problem?

Practice Find the Safest Path in a Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Path With Minimum Effort