LeetCode Problem 2852

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

LeetCode 2852 - Sum of Remoteness of All Cells

Problem Understanding

We are given an n × n grid where each cell is either:

• A positive integer, representing a valid cell with that value.
• -1, representing a blocked cell.

Movement is allowed only between non-blocked cells that share an edge, meaning up, down, left, or right.

For every non-blocked cell (i, j), its remoteness R[i][j] is defined as the sum of values of all non-blocked cells that cannot be reached from (i, j) through valid movements. Blocked cells always have remoteness 0.

The task is to compute:

$$\sum R[i][j]$$

over all cells in the grid.

The key observation is that reachability partitions all non-blocked cells into connected components. Every cell inside the same connected component can reach every other cell in that component. Therefore, for a cell belonging to a component, the unreachable cells are exactly all cells that belong to other components.

The constraints are important:

• n ≤ 300
• The grid can contain up to 300 × 300 = 90,000 cells.
• Cell values can be as large as 10^6.

A solution that performs a graph traversal from every non-blocked cell would be far too slow. We need an algorithm that processes each cell only a constant number of times.

Several edge cases deserve attention:

• The entire grid may consist of blocked cells.
• The grid may contain exactly one connected component.
• Every non-blocked cell may be isolated.
• Cell values can be large, requiring 64-bit arithmetic.
• A single-cell grid should correctly return 0.

Approaches

Brute Force

A straightforward solution would compute R[i][j] independently for every non-blocked cell.

For each cell:

1. Run BFS or DFS to find all reachable cells.
2. Sum the values of all unreachable cells.
3. Add that remoteness value to the final answer.

This is correct because reachability is computed exactly for each cell.

However, if there are k non-blocked cells, we may perform a traversal of up to O(k) cells for each starting cell, resulting in:

$$O(k^2)$$

time complexity.

Since k can be as large as 90,000, this approach is completely infeasible.

Optimal Approach

The important observation is that all cells within the same connected component have exactly the same set of reachable cells.

Suppose:

• totalSum = sum of values of all non-blocked cells.
• A connected component has value sum componentSum.

Then every cell in that component has remoteness:

$$totalSum - componentSum$$

because every cell outside the component is unreachable.

If the component contains size cells, its total contribution to the answer is:

$$size \times (totalSum - componentSum)$$

Therefore:

1. Compute the total value of all non-blocked cells.
2. Find every connected component using DFS, BFS, or Union-Find.
3. For each component, determine:

• Number of cells in the component.
• Sum of values inside the component.

4. Add the component's contribution.

This avoids repeated traversals and processes each cell only once.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k²)	O(k)	Run BFS/DFS from every non-blocked cell
Optimal	O(n²)	O(n²)	Find connected components once

where k is the number of non-blocked cells.

Algorithm Walkthrough

Step 1

Compute the sum of values of all non-blocked cells.

Store this value in totalSum.

This allows us to later compute the unreachable value sum for any component using subtraction rather than explicitly enumerating unreachable cells.

Step 2

Create a visited matrix of size n × n.

This ensures every non-blocked cell is processed exactly once.

Step 3

Iterate through every cell in the grid.

Whenever an unvisited non-blocked cell is found, it must be the start of a new connected component.

Step 4

Perform DFS or BFS from that cell.

During the traversal:

• Count how many cells belong to the component.
• Accumulate the sum of their values.

Let these be:

• componentSize
• componentSum

Step 5

Once the component is fully explored, compute:

$$componentContribution = componentSize \times (totalSum - componentSum)$$

Every cell in the component has remoteness equal to totalSum - componentSum.

Since there are componentSize such cells, multiplying gives the total contribution of the component.

Step 6

Add this contribution to the answer.

Step 7

Continue until all cells have been processed.

Return the accumulated answer.

Why it works

Every non-blocked cell belongs to exactly one connected component. All cells in the same component can reach exactly the same set of cells, namely every cell in that component. Therefore, the unreachable cells for any member of the component are precisely all cells outside the component.

If the sum of all valid cell values is totalSum and the component value sum is componentSum, then the unreachable value sum is totalSum - componentSum. Since every cell in the component has this same remoteness value, multiplying by the component size gives the total contribution of that component. Summing contributions over all components counts every R[i][j] exactly once.

Python Solution

from typing import List
from collections import deque

class Solution:
    def sumRemoteness(self, grid: List[List[int]]) -> int:
        n = len(grid)

        total_sum = 0
        for row in grid:
            for value in row:
                if value != -1:
                    total_sum += value

        visited = [[False] * n for _ in range(n)]
        answer = 0

        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

        for r in range(n):
            for c in range(n):
                if grid[r][c] == -1 or visited[r][c]:
                    continue

                queue = deque([(r, c)])
                visited[r][c] = True

                component_size = 0
                component_sum = 0

                while queue:
                    x, y = queue.popleft()

                    component_size += 1
                    component_sum += grid[x][y]

                    for dx, dy in directions:
                        nx = x + dx
                        ny = y + dy

                        if (
                            0 <= nx < n
                            and 0 <= ny < n
                            and grid[nx][ny] != -1
                            and not visited[nx][ny]
                        ):
                            visited[nx][ny] = True
                            queue.append((nx, ny))

                answer += component_size * (total_sum - component_sum)

        return answer

The implementation begins by computing total_sum, the sum of all non-blocked cell values.

A visited matrix prevents revisiting cells during component exploration.

The outer loops scan every grid position. Whenever an unvisited non-blocked cell is found, a BFS starts from that position. During the BFS, the algorithm tracks both the number of cells in the component and the sum of their values.

After the component has been completely explored, the contribution formula

$$componentSize \times (totalSum - componentSum)$$

is applied and added to the answer.

Because every cell enters the queue at most once, the overall runtime remains linear in the number of grid cells.

Go Solution

func sumRemoteness(grid [][]int) int64 {
	n := len(grid)

	var totalSum int64
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] != -1 {
				totalSum += int64(grid[i][j])
			}
		}
	}

	visited := make([][]bool, n)
	for i := range visited {
		visited[i] = make([]bool, n)
	}

	dirs := [][2]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	var answer int64

	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == -1 || visited[r][c] {
				continue
			}

			queue := [][2]int{{r, c}}
			visited[r][c] = true

			var componentSize int64
			var componentSum int64

			for head := 0; head < len(queue); head++ {
				x := queue[head][0]
				y := queue[head][1]

				componentSize++
				componentSum += int64(grid[x][y])

				for _, d := range dirs {
					nx := x + d[0]
					ny := y + d[1]

					if nx < 0 || nx >= n || ny < 0 || ny >= n {
						continue
					}
					if grid[nx][ny] == -1 || visited[nx][ny] {
						continue
					}

					visited[nx][ny] = true
					queue = append(queue, [2]int{nx, ny})
				}
			}

			answer += componentSize * (totalSum - componentSum)
		}
	}

	return answer
}

Go-Specific Notes

The maximum possible answer exceeds 32-bit integer limits. Therefore all sums and the final answer use int64.

Instead of Python's deque, the Go implementation uses a slice with a moving head index, which provides an efficient queue implementation without repeatedly removing elements from the front.

Worked Examples

Example 1

grid =
[
 [-1,1,-1],
 [5,-1,4],
 [-1,3,-1]
]

Step 1: Compute Total Sum

Cell Value
1
5
4
3

$$totalSum = 1 + 5 + 4 + 3 = 13$$

Step 2: Find Components

Each non-blocked cell is isolated.

Component	Cells	Component Sum	Size
C1	{(0,1)}	1	1
C2	{(1,0)}	5	1
C3	{(1,2)}	4	1
C4	{(2,1)}	3	1

Step 3: Contributions

Component	Contribution
C1	1 × (13 - 1) = 12
C2	1 × (13 - 5) = 8
C3	1 × (13 - 4) = 9
C4	1 × (13 - 3) = 10

$$12 + 8 + 9 + 10 = 39$$

Answer = 39

Example 2

grid =
[
 [-1,3,4],
 [-1,-1,-1],
 [3,-1,-1]
]

Total Sum

$$3 + 4 + 3 = 10$$

Components

Component	Cells	Sum	Size
C1	{(0,1),(0,2)}	7	2
C2	{(2,0)}	3	1

Contributions

Component	Contribution
C1	2 × (10 - 7) = 6
C2	1 × (10 - 3) = 7

$$6 + 7 = 13$$

Answer = 13

Example 3

grid = [[1]]

Total Sum

$$1$$

Components

Component	Sum	Size
C1	1	1

Contribution

$$1 \times (1 - 1) = 0$$

Answer = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every cell is visited at most once
Space	O(n²)	Visited matrix plus BFS queue

The BFS explores each non-blocked cell exactly once. Since there are at most n² cells, the total work performed across all component traversals is O(n²). The visited matrix also requires O(n²) space, and in the worst case the queue may contain O(n²) cells.

Test Cases

sol = Solution()

assert sol.sumRemoteness([[1]]) == 0  # single valid cell

assert sol.sumRemoteness([
    [-1, 1, -1],
    [5, -1, 4],
    [-1, 3, -1]
]) == 39  # example 1

assert sol.sumRemoteness([
    [-1, 3, 4],
    [-1, -1, -1],
    [3, -1, -1]
]) == 13  # example 2

assert sol.sumRemoteness([
    [1, 2],
    [3, 4]
]) == 0  # one connected component

assert sol.sumRemoteness([
    [1, -1],
    [-1, 2]
]) == 3  # two isolated cells

assert sol.sumRemoteness([
    [-1, -1],
    [-1, -1]
]) == 0  # all blocked

assert sol.sumRemoteness([
    [10]
]) == 0  # single cell with large value

assert sol.sumRemoteness([
    [1, 1, 1],
    [1, -1, 1],
    [1, 1, 1]
]) == 0  # component connected around obstacle

assert sol.sumRemoteness([
    [1, -1, 2],
    [-1, -1, -1],
    [3, -1, 4]
]) == 20  # four isolated components

assert sol.sumRemoteness([
    [1000000, -1],
    [-1, 1000000]
]) == 2000000  # verifies large values

Test Summary

Test	Why
[[1]]	Minimum grid size
Example 1	Official example with isolated cells
Example 2	Official example with one multi-cell component
Fully connected 2×2 grid	Remoteness should be zero everywhere
Two isolated cells	Small disconnected case
All blocked cells	No valid cells exist
Single large value	Boundary value check
Connected around obstacle	Verifies proper graph connectivity
Four isolated components	Many disconnected regions
Large values	Confirms 64-bit arithmetic correctness

Edge Cases

All Cells Are Blocked

A grid may contain only -1 values. In this situation there are no connected components and every cell already has remoteness 0.

A buggy implementation might attempt to start traversals from blocked cells or incorrectly compute component contributions. The presented solution skips all blocked cells and therefore returns 0.

One Giant Connected Component

If every non-blocked cell belongs to a single connected component, then every cell can reach every other non-blocked cell.

In that case:

$$totalSum = componentSum$$

and the contribution becomes zero. The algorithm naturally handles this because it computes totalSum - componentSum.

Many Isolated Cells

A checkerboard-like arrangement can create thousands of single-cell components.

A naive solution would repeatedly traverse almost the entire grid for every cell. The optimal solution remains efficient because each isolated cell is discovered exactly once and contributes:

$$1 \times (totalSum - cellValue)$$

to the answer.

Large Cell Values

Each cell value may be as large as 10^6, and there may be up to 90,000 non-blocked cells. The total sum can therefore reach approximately:

$$9 \times 10^{10}$$

which exceeds 32-bit integer limits.

The Python solution uses arbitrary-precision integers automatically, and the Go solution explicitly uses int64 for all accumulated sums and the final answer.