What is the time complexity of Find the Safest Path in a Grid?

The optimal solution has a time complexity of O(n^2 * log(n)).

What is the space complexity of Find the Safest Path in a Grid?

The space complexity is O(n^2).

What data structures are used to solve Find the Safest Path in a Grid?

This problem uses Array, Binary Search, Breadth-First Search, Union Find, Heap (Priority Queue), Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Find the Safest Path in a Grid?

Insight 1: We need to calculate the Manhattan distance of each cell to the nearest thief efficiently. Breadth-First Search (BFS) is suitable for this. Insight 2: Instead of directly searching for the path with the maximum safeness factor, we can use Binary Search. This allows us to check if a path with a given safeness factor exists.

Which companies ask LeetCode 2812. Find the Safest Path in a Grid in interviews?

This problem is frequently asked at IMC, Wells Fargo.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find the Safest Path in a Grid - LeetCode 2812 Solution

Find the Safest Path in a Grid - Complete Solution Guide

Find the Safest Path in a Grid is LeetCode problem 2812, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 ce

Detailed Explanation

The problem asks us to find the maximum 'safeness factor' among all possible paths from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1) in a given n x n grid. The grid contains information about the presence of 'thieves' (represented by 1) and empty cells (represented by 0). The 'safeness factor' of a path is defined as the minimum Manhattan distance from any cell in the path to the nearest thief. The goal is to return the largest possible safeness factor among all valid paths from the start to the end.

Solution Approach

The solution uses a combination of BFS and Binary Search. First, it calculates the distance of each cell in the grid to the nearest thief using BFS. This is stored in a `dist_grid`. Then, it applies Binary Search on the possible safeness factors (from 0 to 2*n, the maximum possible Manhattan distance in the grid). For each potential safeness factor during the Binary Search, another BFS is employed to check if a path exists from (0, 0) to (n-1, n-1) such that all cells on the path have a distance to the nearest thief greater than or equal to the current safeness factor. If such a path exists, we try a higher safeness factor; otherwise, we try a lower one. The final valid safeness factor is the answer.

Step-by-Step Algorithm

Step 1: **Calculate Distance to Nearest Thief:** Perform a BFS starting from all cells containing thieves (grid[r][c] == 1). For each cell, store the minimum Manhattan distance to a thief in `dist_grid`.
Step 2: **Binary Search for Safeness Factor:** Initialize `low` to 0 and `high` to 2*n (maximum possible Manhattan distance). Perform a binary search between `low` and `high` to find the optimal safeness factor.
Step 3: **Check if Path Exists for a Given Safeness Factor:** For each mid-value (potential safeness factor) in the binary search, perform another BFS. This BFS starts at (0, 0) and only explores neighboring cells (r, c) in the grid if `dist_grid[r][c]` is greater than or equal to the potential safeness factor. If this BFS reaches (n-1, n-1), it means a path exists with that safeness factor, and we can try a higher safeness factor. Otherwise, no such path exists, and we need to try a lower safeness factor.
Step 4: **Update Binary Search Range:** Based on whether a path was found in Step 3, update the `low` or `high` pointer for the binary search. If a path was found, increase `low` to `mid + 1`. If no path was found, decrease `high` to `mid - 1`.
Step 5: **Return Result:** The final answer is the largest safeness factor for which a path exists, which is represented by the variable `ans` after the binary search completes.

Key Insights

Insight 1: We need to calculate the Manhattan distance of each cell to the nearest thief efficiently. Breadth-First Search (BFS) is suitable for this.
Insight 2: Instead of directly searching for the path with the maximum safeness factor, we can use Binary Search. This allows us to check if a path with a given safeness factor exists.
Insight 3: To check if a path with a given safeness factor exists, we can use BFS again, but only explore cells whose distance to the nearest thief is greater than or equal to the given safeness factor.

Complexity Analysis

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

Space Complexity: O(n^2)

Topics

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

Companies

Asked at: IMC, Wells Fargo.

Find the Safest Path in a Grid | LeetCode 2812

Medium

Array Binary Search Breadth-First Search Union Find Heap (Priority Queue)Matrix

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

Solution Code

Available in:

import java.util.List;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.PriorityQueue;

class Solution {
    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size();
        
        // Step 1: Multi-source BFS to compute distance from each cell to nearest thief
        Queue<int[]> q = new ArrayDeque<>();
        int[][] dist_grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist_grid[i][j] = -1;
            }
        }

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid.get(r).get(c) == 1) {
                    q.offer(new int[]{r, c});
                    dist_grid[r][c] = 0;
                }
            }
        }
        
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0];
            int c = curr[1];
            int current_dist = dist_grid[r][c];
            
            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                if (0 <= nr && nr < n && 0 <= nc && nc < n && dist_grid[nr][nc] == -1) {
                    dist_grid[nr][nc] = current_dist + 1;
                    q.offer(new int[]{nr, nc});
                }
            }
        }

        // Step 2: Max-heap search to maximize minimum safeness along path
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[2] - a[2]);
        boolean[][] visited = new boolean[n][n];
        
        pq.offer(new int[]{0, 0, dist_grid[0][0]});
        visited[0][0] = true;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int r = curr[0], c = curr[1], safeness = curr[2];

            if (r == n - 1 && c == n - 1) {
                return safeness; // reached destination with max safeness
            }

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

        return -1; // should not reach here
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2812: Find the Safest Path in a Grid - Detailed explanation and solution approaches.

Topics

Array Binary Search Breadth-First Search Union Find Heap (Priority Queue)Matrix

Companies

IMCWells Fargo

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:2812

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: **Calculate Distance to Nearest Thief:** Perform a BFS starting from all cells containing thieves (grid[r][c] == 1). For each cell, store the minimum Manhattan distance to a thief in `dist_grid`.
2
Step 2: **Binary Search for Safeness Factor:** Initialize `low` to 0 and `high` to 2*n (maximum possible Manhattan distance). Perform a binary search between `low` and `high` to find the optimal safeness factor.
3
Step 3: **Check if Path Exists for a Given Safeness Factor:** For each mid-value (potential safeness factor) in the binary search, perform another BFS. This BFS starts at (0, 0) and only explores neighboring cells (r, c) in the grid if `dist_grid[r][c]` is greater than or equal to the potential safeness factor. If this BFS reaches (n-1, n-1), it means a path exists with that safeness factor, and we can try a higher safeness factor. Otherwise, no such path exists, and we need to try a lower safeness factor.
4
Step 4: **Update Binary Search Range:** Based on whether a path was found in Step 3, update the `low` or `high` pointer for the binary search. If a path was found, increase `low` to `mid + 1`. If no path was found, decrease `high` to `mid - 1`.
5
Step 5: **Return Result:** The final answer is the largest safeness factor for which a path exists, which is represented by the variable `ans` after the binary search completes.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2 * log(n))

💾

Space Complexity

O(n^2)

📚 Quadratic space - Uses lots of memory!

📝

Why?

The time complexity is determined by the nested operations. The initial BFS touches each cell once, giving O(n^2). The binary search contributes a factor of O(log(n)). Inside each binary search iteration, the path-checking BFS again visits each cell at most once, resulting in another O(n^2). Multiplying these gives O(n^2 * log(n)). The space complexity is due to storing the distance to the nearest thief for each cell (dist_grid), and also the visited array for the second BFS used for the check function. These each use O(n^2) space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Dijkstra's Algorithm

Instead of binary search and BFS, you could use Dijkstra's algorithm on the grid, treating each cell as a node and edges connecting adjacent cells. The 'weight' of an edge would be related to the safeness factor of the target cell. The goal would be to find the path with the maximum minimum safeness factor using a modified Dijkstra's algorithm.

Time: O(n^2 * log(n)) or O(n^2) depending on heap implementationSpace: O(n^2)

Trade-offs: Dijkstra's might be slightly more efficient in some cases (depending on heap implementation and the grid's layout), but the binary search + BFS approach is more intuitive and easier to implement. The binary search approach is clearer because the path-finding is separated by the safeness factor.

Union Find

We can use Union Find to check if the starting and ending cells are connected with a certain safeness factor. The cells with safeness factor above or equal to the current value can be considered connected. After checking all possible safeness factors, the largest factor connecting the two cells can be chosen as the answer.

Time: O(n^2 log n) for the union find approach with path compression.Space: O(n^2) for the parent array.

Trade-offs: Union Find may be slightly less efficient than BFS due to the overhead of maintaining the disjoint set structure, but can be viable if carefully implemented.

✨

Key Insights

1Insight 1: We need to calculate the Manhattan distance of each cell to the nearest thief efficiently. Breadth-First Search (BFS) is suitable for this.
2Insight 2: Instead of directly searching for the path with the maximum safeness factor, we can use Binary Search. This allows us to check if a path with a given safeness factor exists.
3Insight 3: To check if a path with a given safeness factor exists, we can use BFS again, but only explore cells whose distance to the nearest thief is greater than or equal to the given safeness factor.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: The grid has only one cell (n=1). The solution should correctly handle this case without any errors because the binary search condition and the grid boundary checks are designed to work with n=1.
Edge case 2: There are no thieves in the grid. The initial BFS won't enqueue anything, and dist_grid will remain -1 for all cells. The check function will always return false and the final result will be 0.
Edge case 3: All cells are thieves. The distance to the nearest thief for every cell is 0. The binary search check will only find a path for safeness factor 0.
Edge case 4: No path exists even with a safeness factor of 0. This is when there is a complete blockage on the board by unsafe squares.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering all possible paths from (0, 0) to (n-1, n-1). The problem asks for the *maximum* safeness factor among *all* paths, so a greedy approach that only considers one path is incorrect.

✗Common mistake 2: Incorrectly calculating the Manhattan distance. Remember that it is the sum of the absolute differences of the x and y coordinates.

✗Common mistake 3: Not handling edge cases like empty grids or grids where there are no thieves.

✗Common mistake 4: Using incorrect range during binary search for the safeness factor. The range must be between 0 and 2*n (inclusive).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Path planning for autonomous vehicles in areas with known hazards. The 'thieves' could represent dangerous zones, and the safeness factor would represent the minimum distance the vehicle should maintain from those zones.

🏦Real-world scenario 2: Evacuation route planning during emergencies. The 'thieves' could represent areas affected by a fire or other disaster, and the safeness factor could represent the minimum distance evacuees should maintain from these affected areas.

🎮Real-world scenario 3: Resource allocation in a network. The 'thieves' can represent points of failure or congestion, and the 'safeness factor' is then a measure of robustness against such failures.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I avoid off-by-one errors in binary search?

Use the pattern: left = 0, right = n-1, while (left <= right), mid = left + (right - left) / 2. Decide if you need to find exact match, first occurrence, or last occurrence, and adjust your conditions accordingly. Test with arrays of size 0, 1, and 2.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Find the Safest Path in a Grid"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?