Facebook Pixel

2812. Find the Safest Path in a Grid

MediumBreadth-First SearchUnion FindArrayBinary SearchMatrixHeap (Priority Queue)
Leetcode Link

Problem Description

You are given an n x n grid where each cell can either contain a thief (represented by 1) or be empty (represented by 0). You start at the top-left corner (0, 0) and need to reach the bottom-right corner (n-1, n-1).

From any cell, you can move to its adjacent cells (up, down, left, or right) if they exist within the grid boundaries. You can move through cells containing thieves.

The safeness factor of a path is defined as the minimum Manhattan distance from any cell in that path to any thief in the grid. The Manhattan distance between two cells (a, b) and (x, y) is calculated as |a - x| + |b - y|.

Your task is to find the maximum safeness factor among all possible paths from (0, 0) to (n-1, n-1).

For example, if you have a path where the cells are at distances 3, 5, 2, and 4 from the nearest thief, the safeness factor of that path would be 2 (the minimum distance). You want to find the path that maximizes this minimum distance.

If either the starting position (0, 0) or ending position (n-1, n-1) contains a thief, the safeness factor is 0 since you must pass through a cell with a thief.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The grid can be viewed as a graph where each cell is a node and adjacent cells are connected by edges. We need to find paths from one cell to another.

Is it a tree?

  • No: The grid graph has cycles (you can move in multiple directions and return to the same cell), so it's not a tree structure.

Is the problem related to directed acyclic graphs?

  • No: The grid allows movement in all four directions, creating cycles, so it's not a DAG.

Is the problem related to shortest paths?

  • Yes: We need to find shortest distances from all cells to the nearest thief (Manhattan distance). This is a multi-source shortest path problem.

Is the graph Weighted?

  • No: Each move between adjacent cells has the same cost (distance of 1), making it an unweighted graph.

BFS

  • Yes: For unweighted shortest path problems, BFS is the appropriate algorithm.

Conclusion: The flowchart suggests using BFS for this problem. Specifically, we use multi-source BFS starting from all thief positions simultaneously to calculate the minimum distance from each cell to any thief. This gives us the "safeness" value for each cell. After obtaining these distances, the solution uses additional techniques (Union-Find with sorting) to find the path with maximum safeness factor.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to transform this problem from finding a path with maximum safeness to first understanding what "safeness" means for each cell in the grid.

Think about it this way: if we know the distance from every cell to its nearest thief, then the safeness factor of any path is simply the minimum of these distances along that path. So our first task is to compute the "safeness value" for each cell - which is its distance to the nearest thief.

Since there can be multiple thieves in the grid, we need to find the shortest distance from each cell to ANY thief. This is a classic multi-source BFS problem. We start BFS from all thief positions simultaneously, treating them as distance 0, and propagate outward. Each cell will be reached first by the thief closest to it, giving us the minimum distance.

Now comes the clever part: once we have the safeness value for each cell, how do we find the path from (0,0) to (n-1,n-1) that maximizes the minimum safeness value?

Instead of trying all possible paths (which would be exponential), we can think of it differently: what if we asked "Can we find a path where all cells have safeness value at least k?" If we can answer this yes/no question, we could binary search on k to find the maximum possible value.

But there's an even more elegant approach using Union-Find. If we sort all cells by their safeness values in descending order and add them to our graph one by one, we're essentially building paths that maintain high safeness values. We keep adding cells until (0,0) and (n-1,n-1) become connected. The safeness value of the last cell we add (which has the minimum safeness among all cells in the path) is our answer.

This works because when we add cells in descending order of safeness, the moment the start and end points get connected, we've found a path where every cell has at least that safeness value, and we couldn't do better since any path would need to include cells with lower safeness values.

Learn more about Breadth-First Search, Union Find, Binary Search and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a three-phase approach: computing distances using BFS, sorting cells by safeness values, and using Union-Find to determine the maximum safeness path.

Phase 1: Multi-source BFS for Distance Calculation

First, we initialize a distance matrix dist with infinity values and locate all thieves:

dist = [[inf] * n for _ in range(n)]
q = deque()
for i in range(n):
    for j in range(n):
        if grid[i][j]:  # If cell contains a thief
            q.append((i, j))
            dist[i][j] = 0

Then we perform BFS from all thief positions simultaneously:

dirs = (-1, 0, 1, 0, -1)  # Direction vectors for 4 directions
while q:
    i, j = q.popleft()
    for a, b in pairwise(dirs):  # Check all 4 adjacent cells
        x, y = i + a, j + b
        if 0 <= x < n and 0 <= y < n and dist[x][y] == inf:
            dist[x][y] = dist[i][j] + 1
            q.append((x, y))

The pairwise(dirs) generates pairs like (-1, 0), (0, 1), (1, 0), (0, -1) for the four directions. Each unvisited cell gets assigned a distance one more than its predecessor.

Phase 2: Sorting Cells by Safeness Value

We create a list of all cells with their safeness values and sort in descending order:

q = ((dist[i][j], i, j) for i in range(n) for j in range(n))
q = sorted(q, reverse=True)

This ensures we process cells with higher safeness values first.

Phase 3: Union-Find to Find Maximum Safeness Path

We initialize a Union-Find structure where each cell is represented by a unique ID i * n + j:

uf = UnionFind(n * n)

Then we process cells in order of decreasing safeness:

for d, i, j in q:
    for a, b in pairwise(dirs):
        x, y = i + a, j + b
        if 0 <= x < n and 0 <= y < n and dist[x][y] >= d:
            uf.union(i * n + j, x * n + y)
    if uf.find(0) == uf.find(n * n - 1):
        return int(d)

For each cell (i, j) with safeness d, we union it with adjacent cells that have safeness >= d. This builds connected components of cells with at least safeness d.

The moment cells (0, 0) and (n-1, n-1) belong to the same component (checked by uf.find(0) == uf.find(n * n - 1)), we've found a path where every cell has safeness at least d. Since we process cells in decreasing order of safeness, this d is the maximum possible safeness factor.

The Union-Find data structure efficiently handles the connectivity queries with path compression in find() and union by size in union(), making the overall complexity manageable.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a 3×3 grid:

grid = [[0, 0, 1],
        [0, 0, 0],
        [0, 0, 0]]

Where 1 represents a thief at position (0,2).

Phase 1: Computing Distance to Nearest Thief

We start BFS from the thief position (0,2):

  • Initialize all distances to infinity except thief cell: dist[0][2] = 0
  • From (0,2), we can reach (0,1) and (1,2), setting their distances to 1
  • From (0,1), we reach (1,1) and (0,0), setting their distances to 2 (if not already visited)
  • From (1,2), we reach (2,2), setting its distance to 2
  • Continue until all cells are processed

Final distance matrix:

dist = [[2, 1, 0],
        [3, 2, 1],
        [4, 3, 2]]

Each cell now contains its Manhattan distance to the nearest thief.

Phase 2: Sorting Cells by Safeness Value

We create a list of (safeness, row, col) tuples and sort in descending order:

sorted_cells = [(4, 2, 0), (3, 1, 0), (3, 2, 1), 
                (2, 0, 0), (2, 1, 1), (2, 2, 2),
                (1, 0, 1), (1, 1, 2), (0, 0, 2)]

Phase 3: Union-Find Process

We process cells from highest to lowest safeness:

  1. Add cell (2,0) with safeness 4:

    • No adjacent cells processed yet
    • Start (0,0) and end (2,2) not connected

  2. Add cell (1,0) with safeness 3:

    • Union with (2,0) since dist[2][0] = 4 ≥ 3
    • Start and end still not connected

  3. Add cell (2,1) with safeness 3:

    • Union with (2,0) since dist[2][0] = 4 ≥ 3
    • Now we have component: {(1,0), (2,0), (2,1)}
    • Start and end still not connected

  4. Add cell (0,0) with safeness 2:

    • Union with (1,0) since dist[1][0] = 3 ≥ 2
    • Now (0,0) is in the component

  5. Add cell (1,1) with safeness 2:

    • Union with (1,0) since dist[1][0] = 3 ≥ 2
    • Union with (2,1) since dist[2][1] = 3 ≥ 2
    • Union with (0,0) since dist[0][0] = 2 ≥ 2

  6. Add cell (2,2) with safeness 2:

    • Union with (2,1) since dist[2][1] = 3 ≥ 2
    • Union with (1,1) since dist[1][1] = 2 ≥ 2
    • Now (0,0) and (2,2) are connected!
    • Return safeness value = 2

The maximum safeness factor is 2, achieved by the path: (0,0) → (1,0) → (2,0) → (2,1) → (2,2), where each cell has distance ≥ 2 from the thief.

Solution Implementation

1from collections import deque
2from typing import List
3from itertools import pairwise
4from math import inf
5
6
7class UnionFind:
8    """Union-Find (Disjoint Set Union) data structure with path compression and union by size."""
9  
10    def __init__(self, n: int) -> None:
11        """Initialize Union-Find with n elements."""
12        self.parent = list(range(n))  # Each element is initially its own parent
13        self.size = [1] * n  # Size of each component
14  
15    def find(self, x: int) -> int:
16        """Find the root of element x with path compression."""
17        if self.parent[x] != x:
18            # Path compression: make x point directly to root
19            self.parent[x] = self.find(self.parent[x])
20        return self.parent[x]
21  
22    def union(self, a: int, b: int) -> bool:
23        """
24        Union two elements a and b.
25        Returns True if they were in different sets, False if already connected.
26        """
27        root_a, root_b = self.find(a), self.find(b)
28      
29        if root_a == root_b:
30            return False  # Already in the same set
31      
32        # Union by size: attach smaller tree to larger tree
33        if self.size[root_a] > self.size[root_b]:
34            self.parent[root_b] = root_a
35            self.size[root_a] += self.size[root_b]
36        else:
37            self.parent[root_a] = root_b
38            self.size[root_b] += self.size[root_a]
39      
40        return True
41
42
43class Solution:
44    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
45        """
46        Find the maximum safeness factor for a path from (0,0) to (n-1,n-1).
47        Safeness factor is the minimum distance to any thief along the path.
48        """
49        n = len(grid)
50      
51        # If start or end position has a thief, no safe path exists
52        if grid[0][0] or grid[n - 1][n - 1]:
53            return 0
54      
55        # Step 1: Calculate minimum distance from each cell to nearest thief using BFS
56        queue = deque()
57        distance_to_thief = [[inf] * n for _ in range(n)]
58      
59        # Initialize queue with all thief positions
60        for row in range(n):
61            for col in range(n):
62                if grid[row][col]:  # Found a thief
63                    queue.append((row, col))
64                    distance_to_thief[row][col] = 0
65      
66        # Four directions: up, right, down, left
67        directions = (-1, 0, 1, 0, -1)
68      
69        # BFS to calculate distances
70        while queue:
71            curr_row, curr_col = queue.popleft()
72          
73            # Check all four adjacent cells
74            for delta_row, delta_col in pairwise(directions):
75                next_row = curr_row + delta_row
76                next_col = curr_col + delta_col
77              
78                # Check if the next cell is valid and hasn't been visited
79                if (0 <= next_row < n and 
80                    0 <= next_col < n and 
81                    distance_to_thief[next_row][next_col] == inf):
82                  
83                    distance_to_thief[next_row][next_col] = distance_to_thief[curr_row][curr_col] + 1
84                    queue.append((next_row, next_col))
85      
86        # Step 2: Sort all cells by their distance to thieves (descending order)
87        cells_by_distance = []
88        for row in range(n):
89            for col in range(n):
90                cells_by_distance.append((distance_to_thief[row][col], row, col))
91      
92        cells_by_distance.sort(reverse=True)
93      
94        # Step 3: Use Union-Find to connect cells, starting from highest distance
95        union_find = UnionFind(n * n)
96      
97        for distance, row, col in cells_by_distance:
98            # Try to connect current cell with adjacent cells of same or higher distance
99            for delta_row, delta_col in pairwise(directions):
100                next_row = row + delta_row
101                next_col = col + delta_col
102              
103                if (0 <= next_row < n and 
104                    0 <= next_col < n and 
105                    distance_to_thief[next_row][next_col] >= distance):
106                  
107                    # Connect cells using 1D indexing: row * n + col
108                    union_find.union(row * n + col, next_row * n + next_col)
109          
110            # Check if start and end are connected
111            start_index = 0  # (0, 0) -> 0
112            end_index = n * n - 1  # (n-1, n-1) -> n*n - 1
113          
114            if union_find.find(start_index) == union_find.find(end_index):
115                return int(distance)
116      
117        return 0
118
1class Solution {
2    public int maximumSafenessFactor(List<List<Integer>> grid) {
3        int n = grid.size();
4      
5        // If start or end position has a thief, safeness factor is 0
6        if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) {
7            return 0;
8        }
9      
10        // BFS to calculate minimum distance from each cell to nearest thief
11        Deque<int[]> queue = new ArrayDeque<>();
12        int[][] distanceToThief = new int[n][n];
13        final int INFINITY = 1 << 30;
14      
15        // Initialize all distances to infinity
16        for (int[] row : distanceToThief) {
17            Arrays.fill(row, INFINITY);
18        }
19      
20        // Find all thieves and add them to queue as starting points
21        for (int i = 0; i < n; i++) {
22            for (int j = 0; j < n; j++) {
23                if (grid.get(i).get(j) == 1) {
24                    distanceToThief[i][j] = 0;
25                    queue.offer(new int[] {i, j});
26                }
27            }
28        }
29      
30        // Direction vectors for moving up, right, down, left
31        int[] directions = {-1, 0, 1, 0, -1};
32      
33        // Multi-source BFS to calculate distances
34        while (!queue.isEmpty()) {
35            int[] current = queue.poll();
36            int currentRow = current[0];
37            int currentCol = current[1];
38          
39            // Check all 4 adjacent cells
40            for (int k = 0; k < 4; k++) {
41                int nextRow = currentRow + directions[k];
42                int nextCol = currentCol + directions[k + 1];
43              
44                // If valid cell and not yet visited
45                if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n 
46                    && distanceToThief[nextRow][nextCol] == INFINITY) {
47                    distanceToThief[nextRow][nextCol] = distanceToThief[currentRow][currentCol] + 1;
48                    queue.offer(new int[] {nextRow, nextCol});
49                }
50            }
51        }
52      
53        // Create list of cells sorted by their distance to thieves (descending)
54        List<int[]> cellsByDistance = new ArrayList<>();
55        for (int i = 0; i < n; i++) {
56            for (int j = 0; j < n; j++) {
57                cellsByDistance.add(new int[] {distanceToThief[i][j], i, j});
58            }
59        }
60        cellsByDistance.sort((a, b) -> Integer.compare(b[0], a[0]));
61      
62        // Use Union-Find to connect cells with safeness >= current distance
63        UnionFind unionFind = new UnionFind(n * n);
64      
65        // Process cells from highest to lowest safeness
66        for (int[] cell : cellsByDistance) {
67            int currentDistance = cell[0];
68            int row = cell[1];
69            int col = cell[2];
70          
71            // Connect with adjacent cells that have safeness >= current distance
72            for (int k = 0; k < 4; k++) {
73                int adjacentRow = row + directions[k];
74                int adjacentCol = col + directions[k + 1];
75              
76                if (adjacentRow >= 0 && adjacentRow < n && adjacentCol >= 0 && adjacentCol < n 
77                    && distanceToThief[adjacentRow][adjacentCol] >= currentDistance) {
78                    // Convert 2D coordinates to 1D index for Union-Find
79                    unionFind.union(row * n + col, adjacentRow * n + adjacentCol);
80                }
81            }
82          
83            // Check if start (0,0) and end (n-1,n-1) are connected
84            if (unionFind.find(0) == unionFind.find(n * n - 1)) {
85                return currentDistance;
86            }
87        }
88      
89        return 0;
90    }
91}
92
93class UnionFind {
94    private int[] parent;
95    private int componentCount;
96
97    public UnionFind(int size) {
98        parent = new int[size];
99        // Initially, each element is its own parent
100        for (int i = 0; i < size; i++) {
101            parent[i] = i;
102        }
103        this.componentCount = size;
104    }
105
106    // Union two elements, returns true if they were in different components
107    public boolean union(int a, int b) {
108        int rootA = find(a);
109        int rootB = find(b);
110      
111        if (rootA == rootB) {
112            return false;  // Already in same component
113        }
114      
115        parent[rootA] = rootB;  // Connect component A to component B
116        componentCount--;
117        return true;
118    }
119
120    // Find root of element with path compression
121    public int find(int x) {
122        if (parent[x] != x) {
123            parent[x] = find(parent[x]);  // Path compression
124        }
125        return parent[x];
126    }
127}
128
1class UnionFind {
2public:
3    vector<int> parent;  // Parent array for union-find structure
4    int componentCount;  // Number of connected components
5  
6    // Initialize union-find with n elements
7    UnionFind(int n) : componentCount(n), parent(n) {
8        // Initially, each element is its own parent
9        iota(parent.begin(), parent.end(), 0);
10    }
11  
12    // Unite two elements, returns true if they were in different components
13    bool unite(int a, int b) {
14        int rootA = find(a);
15        int rootB = find(b);
16      
17        // Already in the same component
18        if (rootA == rootB) {
19            return false;
20        }
21      
22        // Connect rootA to rootB
23        parent[rootA] = rootB;
24        componentCount--;
25        return true;
26    }
27  
28    // Find root of element x with path compression
29    int find(int x) {
30        if (parent[x] != x) {
31            parent[x] = find(parent[x]);  // Path compression
32        }
33        return parent[x];
34    }
35};
36
37class Solution {
38public:
39    int maximumSafenessFactor(vector<vector<int>>& grid) {
40        int n = grid.size();
41      
42        // If start or end position is a thief, no safe path exists
43        if (grid[0][0] || grid[n - 1][n - 1]) {
44            return 0;
45        }
46      
47        // BFS to calculate minimum distance from each cell to nearest thief
48        queue<pair<int, int>> bfsQueue;
49        int distance[n][n];
50        memset(distance, 0x3f, sizeof(distance));  // Initialize with large value
51      
52        // Add all thief positions to queue as starting points
53        for (int row = 0; row < n; ++row) {
54            for (int col = 0; col < n; ++col) {
55                if (grid[row][col] == 1) {  // Found a thief
56                    distance[row][col] = 0;
57                    bfsQueue.emplace(row, col);
58                }
59            }
60        }
61      
62        // Direction vectors for 4 adjacent cells (up, right, down, left)
63        int directions[5] = {-1, 0, 1, 0, -1};
64      
65        // Multi-source BFS to calculate distances
66        while (!bfsQueue.empty()) {
67            auto [currentRow, currentCol] = bfsQueue.front();
68            bfsQueue.pop();
69          
70            // Check all 4 adjacent cells
71            for (int k = 0; k < 4; ++k) {
72                int nextRow = currentRow + directions[k];
73                int nextCol = currentCol + directions[k + 1];
74              
75                // Check bounds and if cell hasn't been visited
76                if (nextRow >= 0 && nextRow < n && 
77                    nextCol >= 0 && nextCol < n && 
78                    distance[nextRow][nextCol] == 0x3f3f3f3f) {
79                  
80                    distance[nextRow][nextCol] = distance[currentRow][currentCol] + 1;
81                    bfsQueue.emplace(nextRow, nextCol);
82                }
83            }
84        }
85      
86        // Store all cells with their distance values
87        vector<tuple<int, int, int>> cellsWithDistance;
88        for (int row = 0; row < n; ++row) {
89            for (int col = 0; col < n; ++col) {
90                cellsWithDistance.emplace_back(distance[row][col], row, col);
91            }
92        }
93      
94        // Sort cells by distance in descending order
95        sort(cellsWithDistance.begin(), cellsWithDistance.end());
96        reverse(cellsWithDistance.begin(), cellsWithDistance.end());
97      
98        // Use Union-Find to connect cells
99        UnionFind uf(n * n);
100      
101        // Process cells from highest to lowest distance
102        for (auto [currentDistance, row, col] : cellsWithDistance) {
103            // Try to connect with adjacent cells that have distance >= currentDistance
104            for (int k = 0; k < 4; ++k) {
105                int adjacentRow = row + directions[k];
106                int adjacentCol = col + directions[k + 1];
107              
108                // Check bounds and distance condition
109                if (adjacentRow >= 0 && adjacentRow < n && 
110                    adjacentCol >= 0 && adjacentCol < n && 
111                    distance[adjacentRow][adjacentCol] >= currentDistance) {
112                  
113                    // Connect current cell with adjacent cell
114                    uf.unite(row * n + col, adjacentRow * n + adjacentCol);
115                }
116            }
117          
118            // Check if start and end are connected
119            if (uf.find(0) == uf.find(n * n - 1)) {
120                return currentDistance;  // Maximum safeness factor found
121            }
122        }
123      
124        return 0;  // No path exists
125    }
126};
127
1// Parent array for Union-Find data structure
2let parent: number[];
3// Number of connected components
4let componentCount: number;
5
6/**
7 * Find the root parent of element x with path compression
8 * @param x - The element to find the root for
9 * @returns The root parent of element x
10 */
11function find(x: number): number {
12    if (parent[x] !== x) {
13        // Path compression: make x point directly to root
14        parent[x] = find(parent[x]);
15    }
16    return parent[x];
17}
18
19/**
20 * Union two elements into the same set
21 * @param a - First element
22 * @param b - Second element
23 * @returns true if union was performed, false if already in same set
24 */
25function union(a: number, b: number): boolean {
26    const rootA = find(a);
27    const rootB = find(b);
28  
29    if (rootA !== rootB) {
30        // Merge the two sets by making one root point to the other
31        parent[rootA] = rootB;
32        componentCount--;
33        return true;
34    }
35    return false;
36}
37
38/**
39 * Find the maximum safeness factor for a path from top-left to bottom-right
40 * The safeness factor is the minimum distance to any thief (cell with value 1)
41 * @param grid - 2D grid where 1 represents a thief and 0 represents empty cell
42 * @returns Maximum safeness factor of any valid path
43 */
44function maximumSafenessFactor(grid: number[][]): number {
45    const gridSize = grid.length;
46  
47    // If start or end position has a thief, no safe path exists
48    if (grid[0][0] === 1 || grid[gridSize - 1][gridSize - 1] === 1) {
49        return 0;
50    }
51  
52    // Queue for BFS to calculate distances
53    const bfsQueue: number[][] = [];
54    const infinity = 1 << 30;
55  
56    // Initialize distance matrix with infinity
57    const distanceMatrix: number[][] = Array(gridSize)
58        .fill(0)
59        .map(() => Array(gridSize).fill(infinity));
60  
61    // Find all thieves and add them to BFS queue
62    for (let row = 0; row < gridSize; ++row) {
63        for (let col = 0; col < gridSize; ++col) {
64            if (grid[row][col] === 1) {
65                distanceMatrix[row][col] = 0;
66                bfsQueue.push([row, col]);
67            }
68        }
69    }
70  
71    // Direction vectors for moving up, right, down, left
72    const directions = [-1, 0, 1, 0, -1];
73  
74    // BFS to calculate minimum distance from each cell to nearest thief
75    while (bfsQueue.length > 0) {
76        const [currentRow, currentCol] = bfsQueue.shift()!;
77      
78        for (let dir = 0; dir < 4; ++dir) {
79            const nextRow = currentRow + directions[dir];
80            const nextCol = currentCol + directions[dir + 1];
81          
82            // Check if next position is valid and unvisited
83            if (nextRow >= 0 && nextRow < gridSize && 
84                nextCol >= 0 && nextCol < gridSize && 
85                distanceMatrix[nextRow][nextCol] === infinity) {
86              
87                distanceMatrix[nextRow][nextCol] = distanceMatrix[currentRow][currentCol] + 1;
88                bfsQueue.push([nextRow, nextCol]);
89            }
90        }
91    }
92  
93    // Create array of cells with their safeness values
94    const cellsWithSafeness: number[][] = [];
95    for (let row = 0; row < gridSize; ++row) {
96        for (let col = 0; col < gridSize; ++col) {
97            cellsWithSafeness.push([distanceMatrix[row][col], row, col]);
98        }
99    }
100  
101    // Sort cells by safeness value in descending order
102    cellsWithSafeness.sort((a, b) => b[0] - a[0]);
103  
104    // Initialize Union-Find for all cells
105    const totalCells = gridSize * gridSize;
106    parent = Array(totalCells)
107        .fill(0)
108        .map((_, index) => index);
109    componentCount = totalCells;
110  
111    // Process cells from highest to lowest safeness value
112    for (const [safeness, row, col] of cellsWithSafeness) {
113        // Try to connect with adjacent cells that have >= safeness value
114        for (let dir = 0; dir < 4; ++dir) {
115            const adjacentRow = row + directions[dir];
116            const adjacentCol = col + directions[dir + 1];
117          
118            // Check if adjacent cell is valid and has sufficient safeness
119            if (adjacentRow >= 0 && adjacentRow < gridSize && 
120                adjacentCol >= 0 && adjacentCol < gridSize && 
121                distanceMatrix[adjacentRow][adjacentCol] >= safeness) {
122              
123                // Convert 2D coordinates to 1D index
124                union(row * gridSize + col, adjacentRow * gridSize + adjacentCol);
125            }
126        }
127      
128        // Check if start and end are connected
129        if (find(0) === find(totalCells - 1)) {
130            return safeness;
131        }
132    }
133  
134    return 0;
135}
136

Time and Space Complexity

Time Complexity: O(n² × log n)

Breaking down the algorithm:

  1. BFS for distance calculation: The initial BFS traverses all n² cells exactly once, taking O(n²) time.
  2. Sorting all cells: We sort n² cells by their distance values, which takes O(n² × log(n²)) = O(n² × 2log n) = O(n² × log n) time.
  3. Union-Find operations: For each of the n² cells, we:
    • Perform up to 4 union operations with neighbors
    • Check if start and end are connected
    With path compression and union by size, each find operation is nearly O(1) amortized (specifically O(α(n²)) where α is the inverse Ackermann function, which is effectively constant). So this phase takes O(n²) time.

The dominant operation is sorting, giving us O(n² × log n) overall time complexity.

Space Complexity: O(n²)

The space usage includes:

  1. Distance matrix dist: n × n grid storing distances = O(n²)
  2. Union-Find structure: Arrays p and size each of size n² = O(n²)
  3. BFS queue: At most O(n²) elements
  4. Sorted list q: Contains all n² cells = O(n²)

All components use O(n²) space, resulting in O(n²) total space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Edge Cases with All Thieves

Pitfall: When the grid contains only thieves (all cells have value 1), the BFS initialization adds all cells to the queue with distance 0, but the algorithm still tries to find a path. This can lead to returning 0 when it should, but the logic isn't immediately clear and could be confusing or lead to errors if modified.

Solution: Add an explicit check after BFS to handle this case more clearly:

# After BFS distance calculation
if distance_to_thief[0][0] == 0 and distance_to_thief[n-1][n-1] == 0:
    return 0  # No safe path possible

2. Floating Point Comparison Issues

Pitfall: Using inf from math module returns a float, and later comparing distance_to_thief[next_row][next_col] >= distance mixes float infinity with integers. While Python handles this correctly, it can cause subtle bugs in other languages or if the code is modified.

Solution: Use a large integer constant instead:

INF = n * n  # Maximum possible distance in an n×n grid
distance_to_thief = [[INF] * n for _ in range(n)]
# Later in BFS:
if distance_to_thief[next_row][next_col] == INF:
    # Process unvisited cell

3. Memory Inefficiency in Sorting

Pitfall: Creating a list of all cells with their distances cells_by_distance requires O(n²) extra space and sorting takes O(n²log n) time. For large grids, this becomes a bottleneck.

Solution: Use binary search with BFS validation instead:

def canReachWithSafeness(self, grid, min_safeness):
    """Check if we can reach destination with at least min_safeness"""
    n = len(grid)
    if distance_to_thief[0][0] < min_safeness or distance_to_thief[n-1][n-1] < min_safeness:
        return False
  
    visited = [[False] * n for _ in range(n)]
    queue = deque([(0, 0)])
    visited[0][0] = True
  
    while queue:
        row, col = queue.popleft()
        if row == n-1 and col == n-1:
            return True
      
        for delta_row, delta_col in pairwise(directions):
            next_row, next_col = row + delta_row, col + delta_col
            if (0 <= next_row < n and 0 <= next_col < n and 
                not visited[next_row][next_col] and 
                distance_to_thief[next_row][next_col] >= min_safeness):
                visited[next_row][next_col] = True
                queue.append((next_row, next_col))
  
    return False

# Then use binary search:
left, right = 0, min(distance_to_thief[0][0], distance_to_thief[n-1][n-1])
while left < right:
    mid = (left + right + 1) // 2
    if canReachWithSafeness(grid, mid):
        left = mid
    else:
        right = mid - 1
return left

4. Confusing Cell Indexing

Pitfall: Converting between 2D coordinates (row, col) and 1D index row * n + col can lead to errors, especially when debugging. A mistake like using row * n + col * n or row + col * n is easy to make.

Solution: Create helper functions for clarity:

def get_index(row, col, n):
    """Convert 2D coordinates to 1D index"""
    return row * n + col

def get_coords(index, n):
    """Convert 1D index back to 2D coordinates"""
    return index // n, index % n

# Usage:
union_find.union(get_index(row, col, n), get_index(next_row, next_col, n))
if union_find.find(get_index(0, 0, n)) == union_find.find(get_index(n-1, n-1, n)):
    return int(distance)

5. Missing Grid Validation

Pitfall: The code assumes the grid is non-empty and square (n×n). If given an empty grid or non-square grid, the code will crash.

Solution: Add input validation:

def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
    if not grid or not grid[0]:
        return 0
  
    n = len(grid)
    if any(len(row) != n for row in grid):
        raise ValueError("Grid must be square")
  
    # Rest of the implementation...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Recommended Readings

BFS Fundamentals

https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More