Domain 2MediumMEDIUM

Count Servers that Communicate

Calculate row and column frequencies to identify 'busy' lines, then count servers in those lines.

Domain: medium•Updated: 2026-09-13
#two-pass counting#frequency arrays#O(m*n)#O(m+n)

Problem Breakdown

We are given a binary matrix grid where 1 represents a server and 0 is empty space. The goal is to return the number of servers that can communicate with at least one other server. Communication occurs if two servers share the same row or column.

Inputs:

  • grid: A 2D list (List[List[int]]) representing the map.
  • Dimensions: mm rows and nn columns (1≤m,n≤2501 \le m, n \le 250).

Outputs:

  • An integer count of communicating servers.

Constraints & Edge Cases:

  • A server is isolated if it is the only 1 in its row AND column (count = 1 for both dimensions). Such a server should not be counted.
  • Grid dimensions are guaranteed ≥1\ge 1, but defensive coding handles empty inputs gracefully.
  • Time limit considerations require an efficient solution better than O(M⋅N2)O(M \cdot N^2).

Intuition

A brute-force approach would check every pair of servers or scan rows/columns for each server, leading to high complexity (O(K⋅(M+N))O(K \cdot (M + N))).

Key Insight: Communication depends on the density of a line. If a row contains k≥2k \ge 2 servers, all those kk servers communicate with each other via that row. Similarly for columns. A server communicates if and only if it resides in a “busy” row (count ≥2\ge 2) OR a “busy” column (count ≥2\ge 2).

This allows us to decouple the logic:

  1. Determine which rows/columns are busy by counting 1s globally.
  2. Iterate through servers and check if they belong to any busy line.

Approach

We utilize a two-pass strategy over the grid data, ensuring O(M⋅N)O(M \cdot N) time complexity:

  1. Pre-computation (Counting):

    • Initialize arrays row_counts of size mm and col_counts of size nn.
    • Traverse the entire grid once to increment counters for every row/column containing a server (grid[i][j] == 1).
  2. Validation & Counting:

    • Iterate through the grid again (or iterate over valid indices).
    • For each cell (i, j) with grid[i][j] == 1:
      • Check if row_counts[i] > 1 OR col_counts[j] > 1.
      • If true, increment the result counter.
  3. Return:

    • Return the final accumulated count of communicating servers.

Complexity Analysis

  • Time Complexity: O(m⋅n)O(m \cdot n). We traverse the grid twice (once to build counts, once to validate). Since we touch each cell a constant number of times (22), this is linear with respect to input size. Given constraints (m,n≤250m,n \le 250), operations are negligible (~62k ops per pass).
  • Space Complexity: O(m+n)O(m + n). We store two auxiliary arrays for row and column counts. This is optimal as we need at least one reference count per dimension to avoid re-scanning lines repeatedly.

Solution

from typing import List

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # Handle edge case for empty input (though constraints say m,n >= 1)
        if not grid or not grid[0]:
            return 0
        
        m = len(grid)
        n = len(grid[0])
        
        # Step 1: Count servers in each row and column
        row_counts = [0] * m
        col_counts = [0] * n
        
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    row_counts[r] += 1
                    col_counts[c] += 1
                    
        # Step 2: Count servers that can communicate
        communicating_servers = 0
        
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    # A server communicates if there is another one 
                    # in the same row OR column (count > 1)
                    if row_counts[r] > 1 or col_counts[c] > 1:
                        communicating_servers += 1
                        
        return communicating_servers

# Example usage for verification:
if __name__ == "__main__":
    sol = Solution()
    
    # Case 2 from description
    grid_2 = [[1,0],[1,1]] 
    print(f"Example 2 Output: {sol.countServers(grid_2)}") 
    
    # Case 3 from description
    grid_3 = [
        [1,1,0,0],
        [0,0,1,0],
        [0,0,1,0],
        [0,0,0,1]
    ] 
    print(f"Example 3 Output: {sol.countServers(grid_3)}")

Edge Cases Handled

  • Isolated Server: If a server is the only 1 in its row and column (e.g., Example 1), both counts will be exactly 1. The condition > 1 ensures it returns False, correctly excluding isolated servers from the count.
  • Empty Grid / Single Row/Col: While constraints say m,n≥1m,n \ge 1, the logic handles single rows or columns naturally (if a row has only one server, that specific cell won’t be counted unless another exists in its column). The initial check if not grid ensures robustness against unexpected null inputs.
  • All Servers Connected: If every row and col has ≥2\ge 2 servers, all 1s are counted. The code correctly sums them up without double-counting because we iterate over cells (not pairs), checking the condition per server instance.