MediumNo. 2852LeetCode Premium
Sum of Remoteness of All Cells — LeetCode 2852 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table, Matrix
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
class Solution:
def sumRemoteness(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int) -> (int, int):
s, t = grid[i][j], 1
grid[i][j] = 0
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and grid[x][y] > 0:
s1, t1 = dfs(x, y)
s, t = s + s1, t + t1
return s, t
n = len(grid)
dirs = (-1, 0, 1, 0, -1)
cnt = sum(x > 0 for row in grid for x in row)
ans = 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x > 0:
s, t = dfs(i, j)
ans += (cnt - t) * s
return ansComplexity
- Time
- O(n2)
- Space · auxiliary
- O(n2)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2852. Sum of Remoteness of All Cells is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0959 | Regions Cut By Slashes | Medium |
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 1202 | Smallest String With Swaps | Medium |
Frequently asked questions
- How hard is LeetCode 2852. Sum of Remoteness of All Cells?
LeetCode 2852. Sum of Remoteness of All Cells is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2852. Sum of Remoteness of All Cells?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 2852. Sum of Remoteness of All Cells?
The Python solution on this page uses O(n2) auxiliary space.
- What topics does LeetCode 2852. Sum of Remoteness of All Cells cover?
LeetCode 2852. Sum of Remoteness of All Cells is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table and Matrix on LeetCode.
- Is LeetCode 2852. Sum of Remoteness of All Cells a premium problem?
Yes. LeetCode 2852. Sum of Remoteness of All Cells is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.