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: rows and columns ().
Outputs:
- An integer count of communicating servers.
Constraints & Edge Cases:
- A server is isolated if it is the only
1in its row AND column (count = 1 for both dimensions). Such a server should not be counted. - Grid dimensions are guaranteed , but defensive coding handles empty inputs gracefully.
- Time limit considerations require an efficient solution better than .
Intuition
A brute-force approach would check every pair of servers or scan rows/columns for each server, leading to high complexity ().
Key Insight: Communication depends on the density of a line. If a row contains servers, all those 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 ) OR a “busy” column (count ).
This allows us to decouple the logic:
- Determine which rows/columns are busy by counting
1s globally. - Iterate through servers and check if they belong to any busy line.
Approach
We utilize a two-pass strategy over the grid data, ensuring time complexity:
-
Pre-computation (Counting):
- Initialize arrays
row_countsof size andcol_countsof size . - Traverse the entire grid once to increment counters for every row/column containing a server (
grid[i][j] == 1).
- Initialize arrays
-
Validation & Counting:
- Iterate through the grid again (or iterate over valid indices).
- For each cell
(i, j)withgrid[i][j] == 1:- Check if
row_counts[i] > 1ORcol_counts[j] > 1. - If true, increment the result counter.
- Check if
-
Return:
- Return the final accumulated count of communicating servers.
Complexity Analysis
- Time Complexity: . We traverse the grid twice (once to build counts, once to validate). Since we touch each cell a constant number of times (), this is linear with respect to input size. Given constraints (), operations are negligible (~62k ops per pass).
- Space Complexity: . 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
1in its row and column (e.g., Example 1), both counts will be exactly 1. The condition> 1ensures it returns False, correctly excluding isolated servers from the count. - Empty Grid / Single Row/Col: While constraints say , 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 gridensures robustness against unexpected null inputs. - All Servers Connected: If every row and col has 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.