2812. Find the Safest Path in a Grid

Find the Safest Path in a Grid (LeetCode 2812) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.

How to solve Find the Safest Path in a Grid

Find the Safest Path in a Grid is a Dijkstra's Algorithm for Shortest Path problem, part of Graph Traversal Patterns (DFS & BFS). Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.

Work towards the solution in these steps:

1. Consider using both BFS and binary search together.
2. Launch a BFS starting from all the cells containing thieves to calculate d[x][y] which is the smallest Manhattan distance from (x, y) to the nearest grid that contains thieves.
3. To check if the bottom-right cell of the grid can be reached through a path of safeness factor v, eliminate all cells (x, y) such that grid[x][y] < v. if (0, 0) and (n - 1, n - 1) are still connected, there exists a path between (0, 0) and (n - 1, n - 1) of safeness factor v.

The reference solution runs in O(n^2) time and O(n^2) space.

The Find the Safest Path in a Grid solution and editorial walks through the full approach with reference code.

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.

Topics and companies

Topics: Array, Binary Search, Breadth-First Search, Union Find, Heap (Priority Queue), Matrix.

How to practise Find the Safest Path in a Grid on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(n^2) space.

Open Find the Safest Path in a Grid in the code editor, or read the Find the Safest Path in a Grid editorial for a worked solution with its approach and complexity analysis.

Where Find the Safest Path in a Grid sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Shortest Path (Dijkstra's Algorithm) subpattern
• The full DSA patterns sheet

Problems related to Find the Safest Path in a Grid

Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

• Minimum Obstacle Removal to Reach Corner — Hard, same subpattern
• Minimum Time to Visit a Cell In a Grid — Hard, same subpattern
• Minimum Weighted Subgraph With the Required Paths — Hard, same subpattern
• Network Delay Time — Medium, same subpattern
• Number of Ways to Arrive at Destination — Medium, same subpattern
• Path with Maximum Probability — Medium, same subpattern

Find the Safest Path in a Grid FAQ