_2852. Sum of Remoteness of All Cells.md

2852. Sum of Remoteness of All Cells

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : January 23, 2025

Last updated : January 23, 2025

---

Related Topics : Array, Hash Table, Depth-First Search, Breadth-First Search, Union Find, Matrix

Acceptance Rate : 70.74 %

---

Notes

The summation for example 1 is:
39
= 12+9+10+8
= 3*(1+4+3+5)
= 3*(sum of unconvered values)


V1:
    In this case, looking at the 2nd example for reference, the value 3 seems
    to originate from the number of connected cells (4 cells are connected so
    we multiply by 3). In the case of the 2nd example, it's mult by 1 since
    one island is 2 cells and 0 for the other since it's an island of 1.


    This ends up being an largest island question where we sum the values instead

V2:
    I realized that I misunderstood the prompt. In this case, it's not multiplying
    by neighboring islands but rather NON neighboring islands. Thus, the equation
    ends up being something along the lines of...

    output = sum(
        (total sum of all islands - current island) * size of island
        for island in islands
        )

---

Solutions

• m2852.py

Python

m2852.py

class Solution:
    def sumRemoteness(self, grid: List[List[int]]) -> int:
        def helper(r: int, c: int, output_vals: List[int] = None) -> List[int] :
            if not output_vals :
                output_vals = [0, 0]
            if not (0 <= r < len(grid)) or not (0 <= c < len(grid[0])) :
                return output_vals
            if grid[r][c] == -1 :
                return output_vals

            output_vals[0] += 1
            output_vals[1] += grid[r][c]
            grid[r][c] = -1

            helper(r + 1, c, output_vals)
            helper(r - 1, c, output_vals)
            helper(r, c + 1, output_vals)
            helper(r, c - 1, output_vals)

            return output_vals

        island_sums = []

        for r in range(len(grid)) :
            for c in range(len(grid[0])) :
                if grid[r][c] == -1 :
                    continue
                island_sums.append(helper(r, c))

        output = 0
        tot_sum = sum([x[1] for x in island_sums])

        for x in island_sums :
            output += (tot_sum - x[1]) * x[0]


        return output