We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Remoteness of All Cells

Number: 3148

Difficulty: Medium

Paid? Yes

Companies: Media.net

Problem Description

Given an n x n grid where each cell is either a positive integer or -1 (representing a blocked cell), we need to compute the sum of remoteness R[i][j] for every cell. For a non-blocked cell (i, j), R[i][j] is defined as the sum of values of all other non-blocked cells that cannot reach (i, j) using moves to adjacent non-blocked cells (up, down, left, right). Blocked cells have R[i][j] equal to 0.

Key Insights

  • The problem reduces to finding connected components among non-blocked cells.
  • Cells belonging to the same connected component can reach each other, while cells in different components cannot.
  • Let S be the total sum of values of all non-blocked cells.
  • For each component, if its aggregate sum is S_comp and the number of cells in that component is count, then each cell in that component has a remoteness of S - S_comp.
  • The overall answer is obtained by summing (S - S_comp) for each non-blocked cell, which equals count * (S - S_comp) for each component.

Space and Time Complexity

Time Complexity: O(n^2) – We traverse all cells in the grid once and perform a DFS/BFS for each component. Space Complexity: O(n^2) – In worst-case scenarios, the recursion/queue used for DFS/BFS and extra storage for visitation will use space proportional to the number of cells.

Solution

We use a graph connectivity approach with either DFS or BFS to find connected components among non-blocked cells:

  1. First, compute the total sum S of all non-blocked cells.
  2. Use a DFS (or BFS) to traverse each connected component. For each component, calculate its sum (S_comp) and number of cells (count).
  3. For every cell in that component, the contribution to the final answer is (S - S_comp). Thus, add count * (S - S_comp) to the answer.
  4. Blocked cells are skipped throughout the process and contribute 0.

This method allows us to avoid repeated searches from every cell by consolidating connected component properties.

Code Solutions

# Python solution using DFS
def sumOfRemoteness(grid):
    n = len(grid)
    total_sum = 0
    # Calculate total sum over non-blocked cells
    for i in range(n):
        for j in range(n):
            if grid[i][j] != -1:
                total_sum += grid[i][j]
                
    visited = [[False] * n for _ in range(n)]
    answer = 0
    
    # Define the directions for adjacent cell movement
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    # DFS function to traverse a component
    def dfs(i, j):
        stack = [(i, j)]
        comp_sum = 0
        count = 0
        # Loop until no more nodes in the stack
        while stack:
            x, y = stack.pop()
            if visited[x][y]:
                continue
            visited[x][y] = True
            comp_sum += grid[x][y]
            count += 1
            # Check all valid adjacent cells
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # Ensure within bounds and non-blocked and not visited
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] != -1 and not visited[nx][ny]:
                    stack.append((nx, ny))
        return comp_sum, count

    # Iterate through every cell to process each connected component
    for i in range(n):
        for j in range(n):
            if grid[i][j] != -1 and not visited[i][j]:
                comp_sum, count = dfs(i, j)
                # For every cell in the component, remoteness is total_sum - comp_sum
                answer += count * (total_sum - comp_sum)
    return answer

# Test cases
print(sumOfRemoteness([[-1,1,-1],[5,-1,4],[-1,3,-1]]))  # Expected output: 39
print(sumOfRemoteness([[-1,3,4],[-1,-1,-1],[3,-1,-1]]))  # Expected output: 13
print(sumOfRemoteness([[1]]))                           # Expected output: 0
← Back to All Questions