Sum of Remoteness of All Cells - Practice Coding Problems

Sum of Remoteness of All Cells - Problem

Array Hash Table Depth-First Search Breadth-First Search Union Find Matrix 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.

Input & Output

Example 1 — Basic Grid

$ Input: grid = [[1,2,3],[4,-1,5]]

› Output: 45

💡 Note: Cell (0,0) can reach (1,0), so remoteness = 2+3+5 = 10. Cell (0,1) can only reach itself, so remoteness = 1+4+3+5 = 13. Similarly for other cells, total = 45.

Example 2 — All Connected

$ Input: grid = [[1,2],[3,4]]

› Output: 0

💡 Note: All cells are connected to each other, so each cell can reach all others. Remoteness of each cell is 0.

Example 3 — All Blocked Except One

$ Input: grid = [[5,-1],[-1,-1]]

› Output: 0

💡 Note: Only one non-blocked cell exists. It cannot reach any other non-blocked cells (there are none), so remoteness = 0.

Constraints

1 ≤ n ≤ 100
grid[i][j] == -1 or 1 ≤ grid[i][j] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Matrix with values and blocked cells (-1)

Find Components

Group connected non-blocked cells

Calculate Remoteness

For each cell: sum of unreachable cells

Key Takeaway

🎯 Key Insight: Group cells into connected components first, then calculate remoteness efficiently using component sums

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is that cells in different connected components contribute to each other's remoteness. Use Union-Find to efficiently group cells into connected components, then calculate component sums. For each cell, its remoteness equals the total sum minus its component's sum. Time: O(n² α(n)), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force BFS	O(n⁴)	O(n²)	For each cell, run BFS to find reachable cells and calculate remoteness
Union-Find Connected Components	O(n² α(n))	O(n²)	Group cells into connected components, then calculate remoteness efficiently

Brute Force BFS — Algorithm Steps

Iterate through each cell in the grid
For each non-blocked cell, run BFS to find all reachable cells
Calculate remoteness as sum of all unreachable non-blocked cells
Sum up all remoteness values

Visualization

Tap to expand

Step-by-Step Walkthrough

Start BFS

Run BFS from current cell to find all reachable cells

Calculate

Remoteness = sum of all cells - sum of reachable cells

Repeat

Do this for every non-blocked cell

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int x, y;
} Point;

typedef struct {
    Point* data;
    int front, rear, capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (Point*)malloc(capacity * sizeof(Point));
    q->front = 0;
    q->rear = 0;
    q->capacity = capacity;
    return q;
}

void enqueue(Queue* q, int x, int y) {
    q->data[q->rear].x = x;
    q->data[q->rear].y = y;
    q->rear++;
}

Point dequeue(Queue* q) {
    Point p = q->data[q->front];
    q->front++;
    return p;
}

bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

long long bfsReachable(int** grid, int n, int startI, int startJ, long long totalSum) {
    bool** visited = (bool**)malloc(n * sizeof(bool*));
    for (int i = 0; i < n; i++) {
        visited[i] = (bool*)calloc(n, sizeof(bool));
    }
    
    Queue* queue = createQueue(n * n);
    enqueue(queue, startI, startJ);
    visited[startI][startJ] = true;
    long long reachableSum = 0;
    
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    while (!isEmpty(queue)) {
        Point curr = dequeue(queue);
        int x = curr.x, y = curr.y;
        reachableSum += grid[x][y];
        
        for (int d = 0; d < 4; d++) {
            int nx = x + directions[d][0], ny = y + directions[d][1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] != -1) {
                visited[nx][ny] = true;
                enqueue(queue, nx, ny);
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        free(visited[i]);
    }
    free(visited);
    free(queue->data);
    free(queue);
    
    return totalSum - reachableSum;
}

long long solution(int** grid, int n) {
    long long totalRemoteness = 0;
    
    // Calculate total sum of all non-blocked cells
    long long totalSum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != -1) {
                totalSum += grid[i][j];
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != -1) {
                totalRemoteness += bfsReachable(grid, n, i, j, totalSum);
            }
        }
    }
    
    return totalRemoteness;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small grids
    int n = 0;
    int** grid = (int**)malloc(100 * sizeof(int*));
    
    // Count rows first
    char* temp = strdup(line);
    char* ptr = temp;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') n++;
        ptr++;
    }
    free(temp);
    
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Parse the grid (simplified for demo)
    // In real implementation, would need proper JSON parsing
    
    long long result = solution(grid, n);
    printf("%lld\n", result);
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

For each of n² cells, we run BFS which takes O(n²) time in worst case

✓ Linear Growth

Space Complexity

O(n²)

BFS queue and visited array can store up to n² cells

⚠ Quadratic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

489 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler