1267. Count Servers that Communicate
- Array
- Depth-First Search
- Breadth-First Search
- Matrix
- Counting
TIME
O(m * n)
SPACE
O(m + n)
Intuition
A server communicates if at least one other server shares its row or its column. The question is not about chains of servers, so no graph search is needed. All that matters per server is whether its row or its column holds two or more servers, and two arrays of counts answer that.
Approach
- Count the servers in each row (
rows[i]) and each column (cols[j]). - Walk the grid again and count every server with
rows[i] > 1orcols[j] > 1.
Complexity
- Time: O(m * n), two passes over the grid
- Space: O(m + n) for the counts
Edge Cases
- Servers only on a diagonal: each is alone in its row and column, so the answer is 0 (example 1)
- A server that shares both a row and a column is still counted once
- An L shape: the corner server links the other two, and all three count (example 2)
- One row or one column: either every server counts (two or more servers) or none does
- An empty grid of zeros: 0
Code
class Solution:
def countServers(self, grid: list[list[int]]) -> int:
"""
1267. Count Servers that Communicate
Time: O(m * n)
Space: O(m + n)
"""
rows = [sum(row) for row in grid]
cols = [sum(col) for col in zip(*grid)]
# A server communicates when its row or its column holds another server.
return sum(
1
for i, row in enumerate(grid)
for j, cell in enumerate(row)
if cell and (rows[i] > 1 or cols[j] > 1)
)/**
* 1267. Count Servers that Communicate
* Time: O(m * n)
* Space: O(m + n)
*/
class Solution {
public int countServers(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] rows = new int[m], 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]++;
}
}
}
// A server communicates when its row or its column holds another server.
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;
}
}