Intuition
A server communicates exactly when its row or its column holds at least one other server, so tally servers per row and per column first, then keep any server whose row count or column count exceeds one.
Explanation
Key idea
A server at cell (i, j) can talk to another server only if some other server shares its row i or its column j. Instead of comparing every pair of servers, we just need to know how many servers are in each row and in each column. A server is "connected" exactly when the count of its own row is greater than 1, or the count of its own column is greater than 1.
Walk-through
Take grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]].
Pass 1 — count servers in every row and column. Scan each cell; when it is a 1, add one to that row's tally and that column's tally.
- Row tallies become
[2, 1, 1, 1](the top row has two servers, every other row has one). - Column tallies become
[1, 1, 2, 1](the third column has two servers, the rest have one).
Pass 2 — decide each server. Visit every server again and keep it if its row tally > 1 or its column tally > 1:
(0,0): row tally 2 > 1 → communicates.(0,1): row tally 2 > 1 → communicates.(1,2): column tally 2 > 1 → communicates.(2,2): column tally 2 > 1 → communicates.(3,3): row tally 1 and column tally 1 → isolated, skip it.
Four servers communicate, so the answer is 4.
Why it is correct
Two servers communicate iff they share a row or a column. If a server's row count is more than one, another server is in that row; likewise for columns. If both counts equal one, it is the only server in its row and column, so it can reach no one.
Complexity
- Time: O(m·n) — two passes over the grid.
- Space: O(m + n) — one tally per row and per column.
Implementation
class Solution {
public int countServers(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] rows = new int[m];
int[] cols = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
rows[i]++;
cols[j]++;
}
}
}
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
count++;
}
}
}
return count;
}
}