Sum of remoteness of all cells

Array Hash Table Depth-First Search Breadth-First Search Union-Find Matrix

70.8% acceptance

Mar 31, 2026

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: If the cell (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). For blocked cells, R[i][j] == 0. Return the sum of R[i][j] over all cells.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn sum_remoteness(grid: Vec<Vec<i32>>) -> i64 {
    let n = grid.len();
    let m = grid[0].len();
    let mut visited = vec![vec![false; m]; n];
    let total_sum: i64 = grid.iter().flat_map(|r| r.iter()).filter(|&&v| v != -1).map(|&v| v as i64).sum();
    let mut ans: i64 = 0;
    let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];
    for i in 0..n {
      for j in 0..m {
        if grid[i][j] != -1 && !visited[i][j] {
          let mut stack = vec![(i, j)];
          visited[i][j] = true;
          let mut comp_sum: i64 = 0;
          let mut comp_size: i64 = 0;
          while let Some((r, c)) = stack.pop() {
            comp_sum += grid[r][c] as i64;
            comp_size += 1;
            for &(dx, dy) in &dirs {
              let nr = r as i32 + dx;
              let nc = c as i32 + dy;
              if nr < 0 || nr >= n as i32 || nc < 0 || nc >= m as i32 { continue; }
              let (nr, nc) = (nr as usize, nc as usize);
              if grid[nr][nc] != -1 && !visited[nr][nc] {
                visited[nr][nc] = true;
                stack.push((nr, nc));
              }
            }
          }
          ans += comp_size * (total_sum - comp_sum);
        }
      }
    }
    ans
  }
}