Count Servers that Communicate — Problem & Solution
Count Servers that Communicate solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Servers that Communicate is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search, Counting, Union Find
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a map of a server centre as an m × n grid, where 1 marks a server and 0 marks an empty cell.
Two servers communicate if they sit in the same row or the same column. Return the number of servers that communicate with at least one other server.
Example 1
Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: The two servers share neither a row nor a column.
Example 2
Input: grid = [[1,0],[1,1]]
Output: 3
Example 3
Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Constraints
1 <= grid.length, grid[i].length <= 8grid[i][j] is 0 or 1.
Hints for Count Servers that Communicate
Hint 1
No graph traversal is needed — a server is connected exactly when its row or its column holds another server.
Hint 2
One pass tallies the servers per row and per column.
Hint 3
A second pass counts every server whose row count or column count exceeds one.
How to solve Count Servers that Communicate
A server communicates iff its row or its column holds another server, so per-row and per-column tallies decide every cell without a traversal.
Approach
- Compute
rowCountandcolCount. - Count servers where
rowCount[r] > 1orcolCount[c] > 1.
Why it works
"At least one other server in the same row or column" is exactly the tally condition; no transitivity is involved.
Complexity
- Time —
O(m · n) - Space —
O(m + n)
Pitfalls
- Do not model this as connected components — the question asks about direct communication only.
Reference solution
Python
def countServers(grid) -> int:
m, n = len(grid), len(grid[0])
row_count = [sum(row) for row in grid]
col_count = [sum(grid[r][c] for r in range(m)) for c in range(n)]
return sum(1 for r in range(m) for c in range(n)
if grid[r][c] == 1 and (row_count[r] > 1 or col_count[c] > 1))Java
public static int countServers(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] rowCount = new int[m];
int[] colCount = new int[n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
rowCount[r]++;
colCount[c]++;
}
}
}
int total = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1 && (rowCount[r] > 1 || colCount[c] > 1)) total++;
}
}
return total;
}C++
int countServers(vector<vector<int>>& grid) {
int m = (int) grid.size(), n = (int) grid[0].size();
vector<int> rowCount(m, 0), colCount(n, 0);
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
rowCount[r]++;
colCount[c]++;
}
}
}
int total = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1 && (rowCount[r] > 1 || colCount[c] > 1)) total++;
}
}
return total;
}JavaScript
var countServers = function(grid) {
const m = grid.length, n = grid[0].length;
const rowCount = new Array(m).fill(0);
const colCount = new Array(n).fill(0);
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) {
rowCount[r]++;
colCount[c]++;
}
}
}
let total = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1 && (rowCount[r] > 1 || colCount[c] > 1)) total++;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)