Remoteness in Linear Time

Approach here could be using either a queue or stack, but basically for each cell, traverse the connected nodes, calculate the sum of the connected notes. To avoid a second pass, use a proxy hash table. At the same time calculate the total sum of the grid. Do another linear pass at the end to calculate the remoteness since you have all the data that you need pre-calculated and stored in the hash tables. Code is down below, cheers, ACC.

Sum of Remoteness of All Cells - LeetCode

2852. Sum of Remoteness of All Cells

Medium

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.

 

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 <= 300
• 1 <= grid[i][j] <= 106 or grid[i][j] == -1

public long SumRemoteness(int[][] grid)
{
    long totalSum = 0;
    Hashtable cellToSumIndex = new Hashtable();
    Hashtable indexToSum = new Hashtable();
    int index = 0;

    for (int r = 0; r < grid.Length; r++)
        for (int c = 0; c < grid[r].Length; c++)
            totalSum += SetConnectedSum(grid, r, c, cellToSumIndex, indexToSum, index++);

    long retVal = 0;
    for (int r = 0; r < grid.Length; r++)
        for (int c = 0; c < grid[r].Length; c++)
        {
            ConnectedCell cc = new ConnectedCell(r, c);
            if (cellToSumIndex.ContainsKey(cc.key))
                retVal += (totalSum - (long)indexToSum[(int)cellToSumIndex[cc.key]]);
        }

    return retVal;
}

private long SetConnectedSum(int[][] grid,
                                int row,
                                int col,
                                Hashtable cellToSumIndex,
                                Hashtable indexToSum,
                                int index)
{
    if (grid[row][col] == -1) return 0L;

    ConnectedCell cc = new ConnectedCell(row, col);
    if (cellToSumIndex.ContainsKey(cc.key)) return 0L;

    long sum = 0;
    Stack stack = new Stack();
    cellToSumIndex.Add(cc.key, index);
    stack.Push(cc);

    while(stack.Count > 0)
    {
        ConnectedCell currentCell = stack.Pop();
        sum += grid[currentCell.row][currentCell.col];

        int[] rowDelta = { 1, -1, 0, 0 };
        int[] colDelta = { 0, 0, 1, -1 };
        for (int i = 0; i < rowDelta.Length; i++)
        {
            int nextRow = currentCell.row + rowDelta[i];
            int nextCol = currentCell.col + colDelta[i];
            if (nextRow >= 0 &&
                nextRow < grid.Length &&
                nextCol >= 0 &&
                nextCol < grid[nextRow].Length &&
                grid[nextRow][nextCol] != -1)
            {
                ConnectedCell nextCell = new ConnectedCell(nextRow, nextCol);
                if (!cellToSumIndex.ContainsKey(nextCell.key))
                {
                    cellToSumIndex.Add(nextCell.key, index);
                    stack.Push(nextCell);
                }
            }
        }
    }

    indexToSum.Add(index, sum);
    return sum;
}

public class ConnectedCell
{
    public int row = 0;
    public int col = 0;
    public int key = 0;

    public ConnectedCell(int row, int col)
    {
        this.row = row;
        this.col = col;

        this.key = row * 305 + col;
    }
}