NeetCode #560LC-1267MediumGraphs
← Back to All Problems#560 · #1267 · Count Servers that Communicate(统计参与通信的服务器)
📌 Problem Statement & Constraints
You are given an
m x n grid where 1 is a server. Two servers communicate if they are in the same row or column. Return the number of servers that communicate with at least one other. Constraints: 1 <= m, n <= 250.💡 Core Algorithmic Approaches
- A server communicates exactly when its row or its column contains at least one other server.
- So precompute the server count per row and per column.
- Then a server counts when
row_count[i] > 1orcol_count[j] > 1. - This is O(m*n) and avoids any graph traversal.
💻 Benchmark Python3 Implementation
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
row_cnt = [sum(row) for row in grid]
col_cnt = [sum(grid[i][j] for i in range(m)) for j in range(n)]
return sum(1 for i in range(m) for j in range(n)
if grid[i][j] and (row_cnt[i] > 1 or col_cnt[j] > 1))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): one pass to count and one to tally.
💾 Space Complexity
O(m + n) for the counts.
⚠️ Interview Pitfalls & Follow-ups
- Using
>= 1instead of> 1: a lone server in its row and column does not communicate. - Building a graph and running connected components: workable but far more code than the counting argument.
- Counting the server itself: the threshold is at least 2 in the row or column, including itself.
- Assuming communication is transitive: only the direct row/column relation matters.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.