Count Servers that Communicate

medium array matrix counting

Problem

You are given an m × n grid where each cell holds 1 for a server or 0 for empty space. Two servers communicate when they share the same row or the same column. Return how many servers can communicate with at least one other server.

Inputgrid = [[1, 0], [1, 1]]

Output3

Server (0,0) shares column 0 with (1,0). The two servers in row 1, (1,0) and (1,1), share that row. All three communicate, so the answer is 3.

grid (rows ; , cells 0/1)

def count_servers(grid):
    R, C = len(grid), len(grid[0])
    row = [sum(r) for r in grid]
    col = [sum(grid[i][j] for i in range(R)) for j in range(C)]
    total = 0
    for i in range(R):
        for j in range(C):
            if grid[i][j] == 1 and (row[i] > 1 or col[j] > 1):
                total += 1
    return total

function countServers(grid) {
  const R = grid.length, C = grid[0].length;
  const row = new Array(R).fill(0), col = new Array(C).fill(0);
  for (let i = 0; i < R; i++) for (let j = 0; j < C; j++) if (grid[i][j] === 1) { row[i]++; col[j]++; }
  let total = 0;
  for (let i = 0; i < R; i++) for (let j = 0; j < C; j++)
    if (grid[i][j] === 1 && (row[i] > 1 || col[j] > 1)) total++;
  return total;
}

class Solution {
    public int countServers(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        int[] row = new int[R], col = new int[C];
        for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) if (grid[i][j] == 1) { row[i]++; col[j]++; }
        int total = 0;
        for (int i = 0; i < R; i++) for (int j = 0; j < C; j++)
            if (grid[i][j] == 1 && (row[i] > 1 || col[j] > 1)) total++;
        return total;
    }
}

int countServers(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size();
    vector<int> row(R), col(C);
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) if (grid[i][j] == 1) { row[i]++; col[j]++; }
    int total = 0;
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++)
        if (grid[i][j] == 1 && (row[i] > 1 || col[j] > 1)) total++;
    return total;
}

Explanation

A server can talk to another server only if there is a second server somewhere in its same row or its same column. Checking each server against the whole grid would be slow, so instead we summarize the grid once.

We build two count arrays: row[i] holds how many servers sit in row i, and col[j] holds how many sit in column j. One sweep over the grid fills both — every time we see a 1 at cell (i, j) we bump row[i] and col[j].

Now a server at (i, j) communicates with someone exactly when its row has more than one server or its column has more than one. So in a second sweep we count every 1 where row[i] > 1 || col[j] > 1. A server alone in both its row and column is isolated and is skipped.

Example: grid = [[1,0],[1,1]]. The row counts are [1, 2] and the column counts are [2, 1]. Server (0,0) is alone in its row but column 0 has two servers, so it counts. Both servers in row 1 count because that row holds two. The total is 3.

This is fast because the row and column totals already capture the whole line — we never re-scan a row or column per server.

Time: O(R·C) Space: O(R+C)