Watch 4 video solutions for Sum of Remoteness of All Cells, a medium level problem involving Array, Hash Table, Depth-First Search. This walkthrough by Programming Live with Larry has 229 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed matrix grid of order n * n. Each cell in this matrix has a value grid[i][j], which is either a positive integer or -1 representing a blocked cell.
You can move from a non-blocked cell to any non-blocked cell that shares an edge.
For any cell (i, j), we represent its remoteness as R[i][j] which is defined as the following:
(i, j) is a non-blocked cell, R[i][j] is the sum of the values grid[x][y] such that there is no path from the non-blocked cell (x, y) to the cell (i, j).R[i][j] == 0.Return the sum of R[i][j] over all cells.
Example 1:
Input: grid = [[-1,1,-1],[5,-1,4],[-1,3,-1]] Output: 39 Explanation: In the picture above, there are four grids. The top-left grid contains the initial values in the grid. Blocked cells are colored black, and other cells get their values as it is in the input. In the top-right grid, you can see the value of R[i][j] for all cells. So the answer would be the sum of them. That is: 0 + 12 + 0 + 8 + 0 + 9 + 0 + 10 + 0 = 39. Let's jump on the bottom-left grid in the above picture and calculate R[0][1] (the target cell is colored green). We should sum up the value of cells that can't be reached by the cell (0, 1). These cells are colored yellow in this grid. So R[0][1] = 5 + 4 + 3 = 12. Now let's jump on the bottom-right grid in the above picture and calculate R[1][2] (the target cell is colored green). We should sum up the value of cells that can't be reached by the cell (1, 2). These cells are colored yellow in this grid. So R[1][2] = 1 + 5 + 3 = 9.
Example 2:
Input: grid = [[-1,3,4],[-1,-1,-1],[3,-1,-1]] Output: 13 Explanation: In the picture above, there are four grids. The top-left grid contains the initial values in the grid. Blocked cells are colored black, and other cells get their values as it is in the input. In the top-right grid, you can see the value of R[i][j] for all cells. So the answer would be the sum of them. That is: 3 + 3 + 0 + 0 + 0 + 0 + 7 + 0 + 0 = 13. Let's jump on the bottom-left grid in the above picture and calculate R[0][2] (the target cell is colored green). We should sum up the value of cells that can't be reached by the cell (0, 2). This cell is colored yellow in this grid. So R[0][2] = 3. Now let's jump on the bottom-right grid in the above picture and calculate R[2][0] (the target cell is colored green). We should sum up the value of cells that can't be reached by the cell (2, 0). These cells are colored yellow in this grid. So R[2][0] = 3 + 4 = 7.
Example 3:
Input: grid = [[1]] Output: 0 Explanation: Since there are no other cells than (0, 0), R[0][0] is equal to 0. So the sum of R[i][j] over all cells would be 0.
Constraints:
1 <= n <= 3001 <= grid[i][j] <= 106 or grid[i][j] == -1Problem Overview: You are given a matrix where each cell contains a value or -1 (blocked). Cells connect in four directions. The remoteness of a cell equals the sum of values of all cells that are not reachable from it. The task is to compute the total remoteness across all non-blocked cells.
Approach 1: Brute Force BFS/DFS from Every Cell (O((m*n)^2) time, O(m*n) space)
Start a traversal from each non-blocked cell and mark all reachable cells using breadth-first search or depth-first search. While exploring, accumulate the sum of values in that reachable region. The remoteness for the starting cell equals totalGridSum - reachableSum. Repeat for every cell and accumulate the results. This approach is straightforward but inefficient because the same connected region gets recomputed many times.
Approach 2: Connected Components with DFS (O(m*n) time, O(m*n) space)
The key observation: every cell in the same connected component can reach the exact same set of cells. Their remoteness values therefore depend only on the component's total value. First compute the sum of all non-blocked cells in the grid. Then scan the matrix and run DFS from each unvisited valid cell to discover its connected component. During DFS, count the number of cells and accumulate their value sum. If a component has sum S and size K, each cell's remoteness equals totalSum - S. The total contribution from this component becomes K * (totalSum - S). This eliminates repeated traversal and processes each cell exactly once.
Approach 3: Union Find Components (O(m*n * α(m*n)) time, O(m*n) space)
You can also treat the grid as a graph and build connected components using Union Find. Iterate through the matrix, union adjacent non-blocked cells, and maintain the sum of values for each root component. After building the structure, compute remoteness for each component using the same formula componentSize * (totalSum - componentSum). Union Find works well if connectivity queries are reused or extended later, but the DFS approach is simpler for this problem.
Recommended for interviews: The DFS connected component strategy is what most interviewers expect. It shows you recognize that all cells in a component share identical reachable sets, reducing redundant traversals. Brute force demonstrates the baseline idea, but collapsing the grid into components and applying the formula K * (totalSum - S) shows strong graph reasoning and optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS/DFS from Every Cell | O((m*n)^2) | O(m*n) | Conceptual baseline or very small grids |
| DFS Connected Components | O(m*n) | O(m*n) | Best general solution; simple and optimal for grid traversal |
| Union Find Components | O(m*n * α(m*n)) | O(m*n) | Useful when connectivity structures must support future queries |