⚡Flashcard Drill➔
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

  1. A server communicates exactly when its row or its column contains at least one other server.
  2. So precompute the server count per row and per column.
  3. Then a server counts when row_count[i] > 1 or col_count[j] > 1.
  4. 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 >= 1 instead 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems