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: 35

💡 Note: Two components: {1,4} with sum 5 and {2,3,5} with sum 10. Cell (0,0): remoteness = 10, Cell (0,1): remoteness = 5, Cell (0,2): remoteness = 5, Cell (1,0): remoteness = 10, Cell (1,2): remoteness = 5. Total = 35.

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

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

✓ Brute Force BFS

⏱️ Time: O(n⁴) Space: O(n²)

For every non-blocked cell, run BFS to find all cells it can reach. The remoteness is the sum of all non-blocked cells minus the sum of reachable cells. This approach is straightforward but inefficient.

Union-Find Connected Components

⏱️ Time: O(n² α(n)) Space: O(n²)

Use Union-Find to identify all connected components in the grid. For each component, calculate the sum of values. Then for each cell, its remoteness is the sum of all values in other components.

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>
#include <ctype.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;
}

void freeQueue(Queue* q) {
    free(q->data);
    free(q);
}

long long bfsReachable(int** grid, int n, int startI, int startJ, long long totalSum) {
    if (grid[startI][startJ] == -1) return 0;
    
    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);
    freeQueue(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** parseGrid(char* input, int* n) {
    char* ptr = input;
    
    // Skip whitespace and find first '['
    while (*ptr && *ptr != '[') ptr++;
    if (!*ptr) return NULL;
    
    // Count rows by counting inner '['
    *n = 0;
    char* temp = ptr + 1;
    while (*temp) {
        if (*temp == '[') (*n)++;
        temp++;
    }
    
    if (*n == 0) return NULL;
    
    // Allocate grid (assume square)
    int** grid = (int**)malloc(*n * sizeof(int*));
    for (int i = 0; i < *n; i++) {
        grid[i] = (int*)malloc(*n * sizeof(int));
    }
    
    // Parse the grid
    ptr++; // skip outer '['
    int row = 0;
    
    while (*ptr && row < *n) {
        // Find start of row '['
        while (*ptr && *ptr != '[') ptr++;
        if (!*ptr) break;
        ptr++; // skip '['
        
        int col = 0;
        while (*ptr && *ptr != ']' && col < *n) {
            // Skip non-numeric characters except '-'
            while (*ptr && !isdigit(*ptr) && *ptr != '-') ptr++;
            if (!*ptr || *ptr == ']') break;
            
            // Parse number
            char* endptr;
            int num = strtol(ptr, &endptr, 10);
            grid[row][col] = num;
            col++;
            ptr = endptr;
        }
        
        // Skip to end of row ']'
        while (*ptr && *ptr != ']') ptr++;
        if (*ptr == ']') ptr++;
        
        row++;
    }
    
    return grid;
}

int main() {
    char input[10000];
    if (!fgets(input, sizeof(input), stdin)) {
        printf("0\n");
        return 0;
    }
    
    int n;
    int** grid = parseGrid(input, &n);
    
    if (!grid) {
        printf("0\n");
        return 0;
    }
    
    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

Sum of Remoteness of All Cells - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler