2812. Find the Safest Path in a Grid - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

Python

import heapq

class SafestPathFinder:
    def maxSafenessFactor(self, grid):
        n = len(grid)
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        distance = [[float('inf')] * n for _ in range(n)]
        q = []

        # BFS from all thieves
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    q.append((r, c))
                    distance[r][c] = 0

        for r, c in q:
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and distance[nr][nc] == float('inf'):
                    distance[nr][nc] = distance[r][c] + 1
                    q.append((nr, nc))

        # Max-safeness factor using a max-heap
        heap = [(-distance[0][0], 0, 0)]  # store as negative for max-heap behavior
        maxSafeness = [[-1] * n for _ in range(n)]
        maxSafeness[0][0] = distance[0][0]

        while heap:
            safeness, r, c = heapq.heappop(heap)
            safeness = -safeness

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    newSafeness = min(safeness, distance[nr][nc])
                    if newSafeness > maxSafeness[nr][nc]:
                        maxSafeness[nr][nc] = newSafeness
                        heapq.heappush(heap, (-newSafeness, nr, nc))

        return maxSafeness[n-1][n-1]

# Example usage
spf = SafestPathFinder()
grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]]
print(spf.maxSafenessFactor(grid))  # Output: 2

Java

import java.util.*;

public class SafestPathFinder {
    private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int maxSafenessFactor(int[][] grid) {
        int n = grid.length;
        int[][] distance = new int[n][n];
        for (int[] row : distance) Arrays.fill(row, Integer.MAX_VALUE);
        Queue<int[]> queue = new LinkedList<>();

        // BFS to calculate distance to the nearest thief
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    queue.offer(new int[]{r, c});
                    distance[r][c] = 0;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int r = pos[0], c = pos[1];
            for (int[] dir : directions) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && distance[nr][nc] == Integer.MAX_VALUE) {
                    distance[nr][nc] = distance[r][c] + 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        // Max-heap-like Dijkstra's for the safest path
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[2] - a[2]);  // Max-heap based on safeness factor
        pq.offer(new int[]{0, 0, distance[0][0]});
        boolean[][] visited = new boolean[n][n];
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int r = cur[0], c = cur[1], safeness = cur[2];

            if (r == n - 1 && c == n - 1) return safeness;
            visited[r][c] = true;

            for (int[] dir : directions) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    int newSafeness = Math.min(safeness, distance[nr][nc]);
                    pq.offer(new int[]{nr, nc, newSafeness});
                }
            }
        }

        return 0;
    }

    public static void main(String[] args) {
        SafestPathFinder spf = new SafestPathFinder();
        int[][] grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
        System.out.println(spf.maxSafenessFactor(grid));  // Output: 2
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int maxSafenessFactor(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<vector<int>> distance(n, vector<int>(n, INT_MAX));
    queue<pair<int, int>> q;

    // BFS to calculate initial distances to the nearest thief
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) {
            if (grid[r][c] == 1) {
                q.push({r, c});
                distance[r][c] = 0;
            }
        }
    }

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (auto& dir : directions) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && distance[nr][nc] == INT_MAX) {
                distance[nr][nc] = distance[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    // Use max-heap for Dijkstra's algorithm to find the path with the max safeness factor
    vector<vector<int>> maxSafeness(n, vector<int>(n, -1));
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({distance[0][0], {0, 0}});
    maxSafeness[0][0] = distance[0][0];

    while (!pq.empty()) {
        auto [safeness, pos] = pq.top(); pq.pop();
        auto [r, c] = pos;

        for (auto& dir : directions) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                int newSafeness = min(safeness, distance[nr][nc]);
                if (newSafeness > maxSafeness[nr][nc]) {
                    maxSafeness[nr][nc] = newSafeness;
                    pq.push({newSafeness, {nr, nc}});
                }
            }
        }
    }

    return maxSafeness[n-1][n-1];
}

int main() {
    vector<vector<int>> grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
    cout << maxSafenessFactor(grid) << endl; // Output: 2
    return 0;
}

JavaScript

class SafestPathFinder {
    constructor() {
        this.directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    }

    maxSafenessFactor(grid) {
        const n = grid.length;
        const distance = Array.from({ length: n }, () => Array(n).fill(Infinity));
        const queue = [];

        for (let r = 0; r < n; r++) {
            for (let c = 0; c < n; c++) {
                if (grid[r][c] === 1) {
                    queue.push([r, c]);
                    distance[r][c] = 0;
                }
            }
        }

        let idx = 0;
        while (idx < queue.length) {
            const [r, c] = queue[idx++];
            for (const [dr, dc] of this.directions) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && distance[nr][nc] === Infinity) {
                    distance[nr][nc] = distance[r][c] + 1;
                    queue.push([nr, nc]);
                }
            }
        }

        const heap = new MaxPriorityQueue({ priority: x => x[2] });
        heap.enqueue([0, 0, distance[0][0]]);

        const visited = Array.from({ length: n }, () => Array(n).fill(false));

        while (!heap.isEmpty()) {
            const { element: [r, c, safeness] } = heap.dequeue();
            if (r === n - 1 && c === n - 1) return safeness;
            if (visited[r][c]) continue;
            visited[r][c] = true;

            for (const [dr, dc] of this.directions) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    const newSafeness = Math.min(safeness, distance[nr][nc]);
                    heap.enqueue([nr, nc, newSafeness]);
                }
            }
        }
        return 0;
    }
}

const spf = new SafestPathFinder();
const grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]];
console.log(spf.maxSafenessFactor(grid)); // Output: 2

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>

#define MAX 400

int grid[MAX][MAX];
int n;

int direction[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};

int maxSafenessFactor(int grid[][MAX], int n) {
    int distance[MAX][MAX];
    bool visited[MAX][MAX];
    memset(distance, INT_MAX, sizeof(distance));
    memset(visited, false, sizeof(visited));
    
    // BFS for shortest distance from any thief
    int qsize = n * n;
    int queue[qsize][2];
    int front = 0, rear = 0;
    
    for(int r = 0; r < n; ++r){
        for(int c = 0; c < n; ++c){
            if(grid[r][c] == 1) {
                queue[rear][0] = r;
                queue[rear][1] = c;
                rear++;
                distance[r][c] = 0;
                visited[r][c] = true;
            }
        }
    }
    
    while (front < rear) {
        int r = queue[front][0], c = queue[front][1];
        front++;
        for (int d = 0; d < 4; ++d) {
            int nr = r + direction[d][0], nc = c + direction[d][1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                visited[nr][nc] = true;
                distance[nr][nc] = distance[r][c] + 1;
                queue[rear][0] = nr;
                queue[rear][1] = nc;
                rear++;
            }
        }
    }

    // Use Dijkstra's rather than simple BFS from (0, 0) due to distance
    int maxSafeness[MAX][MAX];
    int pq[qsize][3];
    int pqSize = 0;
    
    bool used[MAX][MAX];
    memset(used, false, sizeof(used));

    // Initialize dijkstra's variables
    memset(maxSafeness, -1, sizeof(maxSafeness));
    maxSafeness[0][0] = distance[0][0];
    pq[pqSize][0] = 0, pq[pqSize][1] = 0, pq[pqSize][2] = distance[0][0];
    pqSize++;
    
    while (pqSize > 0) {
        // Extract the node with maximum safeness factor
        int maxDistIndex = -1;
        for (int i = 0; i < pqSize; i++) {
            if (maxDistIndex == -1 || pq[i][2] > pq[maxDistIndex][2]) {
                maxDistIndex = i;
            }
        }
        
        int curR = pq[maxDistIndex][0], curC = pq[maxDistIndex][1];
        int curD = pq[maxDistIndex][2];
        
        // Remove from queue
        for (int i = maxDistIndex; i < pqSize - 1; i++) {
            pq[i][0] = pq[i+1][0];
            pq[i][1] = pq[i+1][1];
            pq[i][2] = pq[i+1][2];
        }
        pqSize--;

        if (used[curR][curC]) continue;
        used[curR][curC] = true;

        for (int d = 0; d < 4; ++d) {
            int nr = curR + direction[d][0], nc = curC + direction[d][1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                if (min(curD, distance[nr][nc]) > maxSafeness[nr][nc]) {
                    maxSafeness[nr][nc] = min(curD, distance[nr][nc]);
                    pq[pqSize][0] = nr;
                    pq[pqSize][1] = nc;
                    pq[pqSize][2] = maxSafeness[nr][nc];
                    pqSize++;
                }
            }
        }
    }

    return maxSafeness[n-1][n-1];
}

int main() {
    int gridExample[MAX][MAX] = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
    int n = 3;
    printf("%d\n", maxSafenessFactor(gridExample, n));
    return 0;
}

using System;
using System.Collections.Generic;

public class SafestPathFinder {
    private static int[][] directions = new int[4][] {
        new int[] { 0, 1 },
        new int[] { 1, 0 },
        new int[] { 0, -1 },
        new int[] { -1, 0 }
    };

    public int MaxSafenessFactor(int[][] grid) {
        int n = grid.Length;
        int[][] distance = new int[n][];
        for (int i = 0; i < n; i++)
            distance[i] = new int[n];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                distance[i][j] = int.MaxValue;

        Queue<(int, int)> queue = new Queue<(int, int)>();

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    queue.Enqueue((r, c));
                    distance[r][c] = 0;
                }
            }
        }

        while (queue.Count > 0) {
            var (r, c) = queue.Dequeue();
            foreach (var dir in directions) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && distance[nr][nc] == int.MaxValue) {
                    distance[nr][nc] = distance[r][c] + 1;
                    queue.Enqueue((nr, nc));
                }
            }
        }

        PriorityQueue<(int, int, int)> pq = new();
        pq.Enqueue((0, 0, distance[0][0]));
        bool[,] visited = new bool[n, n];

        while (pq.Count > 0) {
            var (r, c, safeness) = pq.Dequeue();
            if (r == n - 1 && c == n - 1) return safeness;
            if (visited[r, c]) continue;
            visited[r, c] = true;

            foreach (var dir in directions) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr, nc]) {
                    int newSafeness = Math.Min(safeness, distance[nr][nc]);
                    pq.Enqueue((nr, nc, newSafeness));
                }
            }
        }

        return 0;
    }

    public static void Main() {
        SafestPathFinder spf = new SafestPathFinder();
        int[][] grid = new int[][] {
            new int[] { 0, 0, 1 },
            new int[] { 0, 0, 0 },
            new int[] { 0, 0, 0 }
        };
        Console.WriteLine(spf.MaxSafenessFactor(grid));  // Output: 2
    }
}

public class PriorityQueue<T> where T : IComparable<T> {
    private List<T> data = new List<T>();

    public int Count => data.Count;

    public void Enqueue(T item) {
        data.Add(item);
        int ci = data.Count - 1;
        while (ci > 0) {
            int pi = (ci - 1) / 2;
            if (data[ci].CompareTo(data[pi]) <= 0) break;
            var tmp = data[ci];
            data[ci] = data[pi];
            data[pi] = tmp;
            ci = pi;
        }
    }

    public T Dequeue() {
        var ret = data[0];
        var li = data.Count - 1;
        data[0] = data[li];
        data.RemoveAt(li);
        --li;
        int pi = 0;
        while (true) {
            int ci = pi * 2 + 1;
            if (ci > li) break;
            int rc = ci + 1;
            if (rc <= li && data[rc].CompareTo(data[ci]) > 0) ci = rc;
            if (data[pi].CompareTo(data[ci]) >= 0) break;
            var tmp = data[pi];
            data[pi] = data[ci];
            data[ci] = tmp;
            pi = ci;
        }
        return ret;
    }
}

The Python solution uses BFS to precompute distances from all thieves. Then, a max-heap (prioritizing higher safeness) guides traversal from the start to the end, ensuring the net max safeness factor is achieved.

Complexity

Time Complexity: O(n² log n) due to the max-heap operations.
Space Complexity: O(n²) for holding distances and maxima details in heap and arrays.

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.

Python

from collections import deque

class SafestPathFinder:
    def bidirectionalSafenessFactor(self, grid):
        n = len(grid)
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        distFromStart = [[float('inf')] * n for _ in range(n)]
        distFromEnd = [[float('inf')] * n for _ in range(n)]

        qStart = deque([(0, 0)])
        distFromStart[0][0] = 0

        qEnd = deque([(n - 1, n - 1)])
        distFromEnd[n - 1][n - 1] = 0

        while qStart or qEnd:
            if qStart:
                r, c = qStart.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and distFromStart[nr][nc] == float('inf'):
                        distFromStart[nr][nc] = distFromStart[r][c] + 1
                        qStart.append((nr, nc))

            if qEnd:
                r, c = qEnd.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and distFromEnd[nr][nc] == float('inf'):
                        distFromEnd[nr][nc] = distFromEnd[r][c] + 1
                        qEnd.append((nr, nc))

            for i in range(n):
                for j in range(n):
                    if distFromStart[i][j] != float('inf') and distFromEnd[i][j] != float('inf'):
                        return distFromStart[i][j] + distFromEnd[i][j]

        return -1

# Example usage
spf = SafestPathFinder()
grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]]
print(spf.bidirectionalSafenessFactor(grid)) # Output: Safeness factor

Java

import java.util.*;

public class SafestPathFinder {
    private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int bidirectionalSafenessFactor(int[][] grid) {
        int n = grid.length;
        int[][] distFromStart = new int[n][n];
        int[][] distFromEnd = new int[n][n];
        for (int[] row : distFromStart) Arrays.fill(row, Integer.MAX_VALUE);
        for (int[] row : distFromEnd) Arrays.fill(row, Integer.MAX_VALUE);

        Queue<int[]> startQueue = new LinkedList<>();
        startQueue.offer(new int[]{0, 0});
        distFromStart[0][0] = 0;

        Queue<int[]> endQueue = new LinkedList<>();
        endQueue.offer(new int[]{n - 1, n - 1});
        distFromEnd[n - 1][n - 1] = 0;

        while (!startQueue.isEmpty() || !endQueue.isEmpty()) {
            if (!startQueue.isEmpty()) {
                int[] pos = startQueue.poll();
                int r = pos[0], c = pos[1];
                for (int[] dir : directions) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] == Integer.MAX_VALUE) {
                        distFromStart[nr][nc] = distFromStart[r][c] + 1;
                        startQueue.offer(new int[]{nr, nc});
                    }
                }
            }

            if (!endQueue.isEmpty()) {
                int[] pos = endQueue.poll();
                int r = pos[0], c = pos[1];
                for (int[] dir : directions) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromEnd[nr][nc] == Integer.MAX_VALUE) {
                        distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
                        endQueue.offer(new int[]{nr, nc});
                    }
                }
            }

            // Checking overlap
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (distFromStart[i][j] != Integer.MAX_VALUE && distFromEnd[i][j] != Integer.MAX_VALUE) {
                        return distFromStart[i][j] + distFromEnd[i][j];
                    }
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        SafestPathFinder spf = new SafestPathFinder();
        int[][] grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
        System.out.println(spf.bidirectionalSafenessFactor(grid)); // Output: Safeness factor
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int bidirectionalSafenessFactor(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<vector<int>> distFromStart(n, vector<int>(n, INT_MAX));
    vector<vector<int>> distFromEnd(n, vector<int>(n, INT_MAX));

    queue<pair<int, int>> startQueue;
    startQueue.push({0, 0});
    distFromStart[0][0] = 0;

    queue<pair<int, int>> endQueue;
    endQueue.push({n - 1, n - 1});
    distFromEnd[n - 1][n - 1] = 0;

    while (!startQueue.empty() || !endQueue.empty()) {
        if (!startQueue.empty()) {
            auto [r, c] = startQueue.front(); startQueue.pop();
            for (auto& dir : directions) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] == INT_MAX) {
                    distFromStart[nr][nc] = distFromStart[r][c] + 1;
                    startQueue.push({nr, nc});
                }
            }
        }

        if (!endQueue.empty()) {
            auto [r, c] = endQueue.front(); endQueue.pop();
            for (auto& dir : directions) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromEnd[nr][nc] == INT_MAX) {
                    distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
                    endQueue.push({nr, nc});
                }
            }
        }

        // Checking overlap
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (distFromStart[i][j] != INT_MAX && distFromEnd[i][j] != INT_MAX) {
                    return distFromStart[i][j] + distFromEnd[i][j];
                }
            }
        }
    }

    return -1;
}

int main() {
    vector<vector<int>> grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
    cout << bidirectionalSafenessFactor(grid) << endl; // Output: Safeness factor
    return 0;
}

JavaScript

class SafestPathFinder {
    constructor() {
        this.directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    }

    bidirectionalSafenessFactor(grid) {
        const n = grid.length;
        const distFromStart = Array.from({ length: n }, () => Array(n).fill(Infinity));
        const distFromEnd = Array.from({ length: n }, () => Array(n).fill(Infinity));

        const startQueue = [[0, 0]];
        distFromStart[0][0] = 0;

        const endQueue = [[n - 1, n - 1]];
        distFromEnd[n - 1][n - 1] = 0;

        while (startQueue.length || endQueue.length) {
            if (startQueue.length) {
                const [r, c] = startQueue.shift();
                for (const [dr, dc] of this.directions) {
                    const nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] === Infinity) {
                        distFromStart[nr][nc] = distFromStart[r][c] + 1;
                        startQueue.push([nr, nc]);
                    }
                }
            }

            if (endQueue.length) {
                const [r, c] = endQueue.shift();
                for (const [dr, dc] of this.directions) {
                    const nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromEnd[nr][nc] === Infinity) {
                        distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
                        endQueue.push([nr, nc]);
                    }
                }
            }

            // Check overlap
            for (let i = 0; i < n; ++i) {
                for (let j = 0; j < n; ++j) {
                    if (distFromStart[i][j] !== Infinity && distFromEnd[i][j] !== Infinity) {
                        return distFromStart[i][j] + distFromEnd[i][j];
                    }
                }
            }
        }

        return -1;
    }
}

const spf = new SafestPathFinder();
const grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]];
console.log(spf.bidirectionalSafenessFactor(grid)); // Output: Safeness factor

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>

#define MAX 400

int grid[MAX][MAX];
int n;

int direction[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};

int bidirectionalSafenessFactor(int grid[][MAX], int n) {
    // Distance from start and end
    int distanceStart[MAX][MAX];
    int distanceEnd[MAX][MAX];

    memset(distanceStart, INT_MAX, sizeof(distanceStart));
    memset(distanceEnd, INT_MAX, sizeof(distanceEnd));

    // BFS start queue
    int queueStart[MAX*MAX][2];
    int frontStart = 0, rearStart = 0;

    queueStart[rearStart][0] = 0;
    queueStart[rearStart][1] = 0;
    rearStart++;
    distanceStart[0][0] = 0;

    // BFS end queue
    int queueEnd[MAX*MAX][2];
    int frontEnd = 0, rearEnd = 0;

    queueEnd[rearEnd][0] = n-1;
    queueEnd[rearEnd][1] = n-1;
    rearEnd++;
    distanceEnd[n-1][n-1] = 0;

    while (frontStart < rearStart && frontEnd < rearEnd) {
        // Expand from start
        int r = queueStart[frontStart][0], c = queueStart[frontStart][1];
        frontStart++;
        
        for (int d = 0; d < 4; ++d) {
            int nr = r + direction[d][0], nc = c + direction[d][1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && distanceStart[nr][nc] == INT_MAX) {
                distanceStart[nr][nc] = distanceStart[r][c] + 1;
                queueStart[rearStart][0] = nr;
                queueStart[rearStart][1] = nc;
                rearStart++;
            }
        }

        // Expand from end
        r = queueEnd[frontEnd][0], c = queueEnd[frontEnd][1];
        frontEnd++;

        for (int d = 0; d < 4; ++d) {
            int nr = r + direction[d][0], nc = c + direction[d][1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && distanceEnd[nr][nc] == INT_MAX) {
                distanceEnd[nr][nc] = distanceEnd[r][c] + 1;
                queueEnd[rearEnd][0] = nr;
                queueEnd[rearEnd][1] = nc;
                rearEnd++;
            }
        }

        // Check overlap
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (distanceStart[i][j] != INT_MAX && distanceEnd[i][j] != INT_MAX) {
                    return distanceStart[i][j] + distanceEnd[i][j];
                }
            }
        }
    }
    
    return -1;
}

int main() {
    int gridExample[MAX][MAX] = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
    int n = 3;
    printf("%d\n", bidirectionalSafenessFactor(gridExample, n));
    return 0;
}

using System;
using System.Collections.Generic;

public class SafestPathFinder {
    private static int[][] directions = new int[4][] {
        new int[] { 0, 1 },
        new int[] { 1, 0 },
        new int[] { 0, -1 },
        new int[] { -1, 0 }
    };

    public int BidirectionalSafenessFactor(int[][] grid) {
        int n = grid.Length;
        int[][] distFromStart = new int[n][];
        int[][] distFromEnd = new int[n][];
        for (int i = 0; i < n; i++) {
            distFromStart[i] = new int[n];
            distFromEnd[i] = new int[n];
            Array.Fill(distFromStart[i], int.MaxValue);
            Array.Fill(distFromEnd[i], int.MaxValue);
        }

        Queue<(int, int)> startQueue = new();
        startQueue.Enqueue((0, 0));
        distFromStart[0][0] = 0;

        Queue<(int, int)> endQueue = new();
        endQueue.Enqueue((n - 1, n - 1));
        distFromEnd[n - 1][n - 1] = 0;

        while (startQueue.Count > 0 || endQueue.Count > 0) {
            if (startQueue.Count > 0) {
                var (r, c) = startQueue.Dequeue();
                foreach (var dir in directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] == int.MaxValue) {
                        distFromStart[nr][nc] = distFromStart[r][c] + 1;
                        startQueue.Enqueue((nr, nc));
                    }
                }
            }

            if (endQueue.Count > 0) {
                var (r, c) = endQueue.Dequeue();
                foreach (var dir in directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromEnd[nr][nc] == int.MaxValue) {
                        distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
                        endQueue.Enqueue((nr, nc));
                    }
                }
            }

            // Check overlapping
data switching
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (distFromStart[i][j] != int.MaxValue && distFromEnd[i][j] != int.MaxValue) {
                        return distFromStart[i][j] + distFromEnd[i][j];
                    }
                }
            }
        }

        return -1;
    }

    public static void Main() {
        SafestPathFinder spf = new();
        int[][] grid = new int[][] {
            new int[] { 0, 0, 1 },
            new int[] { 0, 0, 0 },
            new int[] { 0, 0, 0 }
        };
        Console.WriteLine(spf.BidirectionalSafenessFactor(grid)); // Output: Safeness factor
    }
}

The Python solution deploys bidirectional BFS to handle both source and target expansions concurrently. This not only improves exploration efficiency but also allows quicker discovery of overlapping safe paths.

Complexity

Time Complexity: O(n²), because of dual BFS processing on the grid.
Space Complexity: O(n²), needed for tracking relationship distances from both path directions.

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.

TypeScript

class UnionFind {
    private p: number[];
    private n: number;

    constructor(n: number) {
        this.n = n;
        this.p = Array(n)
            .fill(0)
            .map((_, i) => i);
    }

    find(x: number): number {
        if (this.p[x] !== x) {
            this.p[x] = this.find(this.p[x]);
        }
        return this.p[x];
    }

    union(a: number, b: number): boolean {
        const pa = this.find(a);
        const pb = this.find(b);
        if (pa !== pb) {
            this.p[pa] = pb;
            this.n--;
            return true;
        }
        return false;
    }
}

function maximumSafenessFactor(grid: number[][]): number {
    const n = grid.length;
    if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) {
        return 0;
    }
    const q: number[][] = [];
    const inf = 1 << 30;
    const dist: number[][] = Array(n)
        .fill(0)
        .map(() => Array(n).fill(inf));
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] === 1) {
                dist[i][j] = 0;
                q.push([i, j]);
            }
        }
    }
    const dirs = [-1, 0, 1, 0, -1];
    while (q.length) {
        const [i, j] = q.shift()!;
        for (let k = 0; k < 4; ++k) {
            const [x, y] = [i + dirs[k], j + dirs[k + 1]];
            if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] === inf) {
                dist[x][y] = dist[i][j] + 1;
                q.push([x, y]);
            }
        }
    }
    const t: number[][] = [];
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            t.push([dist[i][j], i, j]);
        }
    }
    t.sort((a, b) => b[0] - a[0]);
    const uf = new UnionFind(n * n);
    for (const [d, i, j] of t) {
        for (let k = 0; k < 4; ++k) {
            const [x, y] = [i + dirs[k], j + dirs[k + 1]];
            if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] >= d) {
                uf.union(i * n + j, x * n + y);
            }
        }
        if (uf.find(0) == uf.find(n * n - 1)) {
            return d;
        }
    }
    return 0;
}

type unionFind struct {
	p []int
	n int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	return &unionFind{p, n}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	if uf.find(a) == uf.find(b) {
		return false
	}
	uf.p[uf.find(a)] = uf.find(b)
	uf.n--
	return true
}

func maximumSafenessFactor(grid [][]int) int {
	n := len(grid)
	if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
		return 0
	}
	q := [][2]int{}
	dist := make([][]int, n)
	const inf = 1 << 30
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			dist[i][j] = inf
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				dist[i][j] = 0
				q = append(q, [2]int{i, j})
			}
		}
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		i, j := p[0], p[1]
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < n && y >= 0 && y < n && dist[x][y] == inf {
				dist[x][y] = dist[i][j] + 1
				q = append(q, [2]int{x, y})
			}
		}
	}
	t := [][3]int{}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			t = append(t, [3]int{dist[i][j], i, j})
		}
	}
	sort.Slice(t, func(i, j int) bool {
		return t[i][0] > t[j][0]
	})
	uf := newUnionFind(n * n)
	for _, p := range t {
		d, i, j := p[0], p[1], p[2]
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < n && y >= 0 && y < n && dist[x][y] >= d {
				uf.union(i*n+j, x*n+y)
			}
		}
		if uf.find(0) == uf.find(n*n-1) {
			return d
		}
	}
	return 0
}

Rust

use std::collections::VecDeque;
impl Solution {
    fn dfs(i: usize, j: usize, v: i32, g: &Vec<Vec<i32>>, vis: &mut Vec<Vec<bool>>) -> bool {
        if vis[i][j] || g[i][j] <= v {
            return false;
        }
        vis[i][j] = true;
        let n = g.len();
        (i == n - 1 && j == n - 1)
            || (i != 0 && Self::dfs(i - 1, j, v, g, vis))
            || (i != n - 1 && Self::dfs(i + 1, j, v, g, vis))
            || (j != 0 && Self::dfs(i, j - 1, v, g, vis))
            || (j != n - 1 && Self::dfs(i, j + 1, v, g, vis))
    }

    pub fn maximum_safeness_factor(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut g = vec![vec![-1; n]; n];
        let mut q = VecDeque::new();
        for i in 0..n {
            for j in 0..n {
                if grid[i][j] == 1 {
                    q.push_back((i, j));
                }
            }
        }
        let mut level = 0;
        while !q.is_empty() {
            let m = q.len();
            for _ in 0..m {
                let (i, j) = q.pop_front().unwrap();
                if g[i][j] != -1 {
                    continue;
                }
                g[i][j] = level;
                if i != n - 1 {
                    q.push_back((i + 1, j));
                }
                if i != 0 {
                    q.push_back((i - 1, j));
                }
                if j != n - 1 {
                    q.push_back((i, j + 1));
                }
                if j != 0 {
                    q.push_back((i, j - 1));
                }
            }
            level += 1;
        }
        let mut left = 0;
        let mut right = level;
        while left < right {
            let mid = (left + right) >> 1;
            if Self::dfs(0, 0, mid, &g, &mut vec![vec![false; n]; n]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        right
    }
}

Try this approach in the editor

Approach 4: Default Approach

TypeScript

function maximumSafenessFactor(grid: number[][]): number {
    const n = grid.length;
    const g = Array.from({ length: n }, () => new Array(n).fill(-1));
    const vis = Array.from({ length: n }, () => new Array(n).fill(false));
    let q: [number, number][] = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                q.push([i, j]);
            }
        }
    }
    let level = 0;
    while (q.length) {
        const t: [number, number][] = [];
        for (const [x, y] of q) {
            if (x < 0 || y < 0 || x === n || y === n || g[x][y] !== -1) {
                continue;
            }
            g[x][y] = level;
            t.push([x + 1, y]);
            t.push([x - 1, y]);
            t.push([x, y + 1]);
            t.push([x, y - 1]);
        }
        q = t;
        level++;
    }
    const dfs = (i: number, j: number, v: number) => {
        if (i < 0 || j < 0 || i === n || j === n || vis[i][j] || g[i][j] <= v) {
            return false;
        }
        vis[i][j] = true;
        return (
            (i === n - 1 && j === n - 1) ||
            dfs(i + 1, j, v) ||
            dfs(i, j + 1, v) ||
            dfs(i - 1, j, v) ||
            dfs(i, j - 1, v)
        );
    };

    let left = 0;
    let right = level;
    while (left < right) {
        vis.forEach(v => v.fill(false));
        const mid = (left + right) >>> 1;
        if (dfs(0, 0, mid)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return right;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
BFS with Distance Preprocessing	Time Complexity: O(n² log n) due to the max-heap operations. Space Complexity: O(n²) for holding distances and maxima details in heap and arrays.
Bidirectional BFS	Time Complexity: O(n²), because of dual BFS processing on the grid. Space Complexity: O(n²), needed for tracking relationship distances from both path directions.
BFS + Sorting + Union-Find	–
Default Approach	–

Complexity analysis

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

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.

Find the Safest Path in a Grid solution and explanation

The problem

Approach overview

Approach 1: BFS with Distance Preprocessing

Approach 2: Bidirectional BFS

Approach 3: BFS + Sorting + Union-Find

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Safest Path in a Grid solution and explanation

The problem

Approach overview

Approach 1: BFS with Distance Preprocessing

Approach 2: Bidirectional BFS

Approach 3: BFS + Sorting + Union-Find

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems