Count Servers that Communicate

4 min readJan 23, 2025

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

Problem Intuition:

The core idea revolves around understanding that a server is considered “connected” if it has at least one other server in its row or column.

Isolation: An isolated server exists solely in its row or column, having no other server to communicate with.
Connectivity: A connected server, on the other hand, can potentially communicate with other servers within its row or column.

Approach Intuition

Count Row and Column Occupancies:

By iterating through the grid, we can efficiently count the number of servers present in each row and each column. This information is crucial to determine if a server is isolated or connected.

Identify Connected Servers:

We then revisit each cell in the grid.
If a cell contains a server and either its row or column has more than one server, we can conclude that this server is connected to at least one other server.

Why This Works

Row/Column Connection: If a server’s row or column has multiple servers, it implies that the server can potentially communicate with other servers within that row or column.
Efficiency: Counting the number of servers in each row and column provides a concise and efficient way to determine connectivity.

In essence, the problem boils down to identifying and counting servers that are not isolated within their respective rows and columns.

Solution:

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        row = len(grid)
        column = len(grid[0])

        row_cnt = [0] * row
        column_cnt = [0] * column
        for r in range(row):
            for c in range(column):
                if grid[r][c] == 1:
                    row_cnt[r] += 1 
                    column_cnt[c] += 1
        res = 0
        for r in range(row):
            for c in range(column):
                if grid[r][c] == 1 and (row_cnt[r] > 1 or column_cnt[c] > 1):
                    res += 1
        return res

Solution Approach:

Initialization:

Initialize two lists: row_cnt to store the count of servers in each row, and column_cnt to store the count of servers in each column. Both lists are initially filled with zeros.

Count Servers in Rows and Columns:

Iterate through the grid:
If a cell contains a server (grid[r][c] == 1):
Increment the count of servers in the corresponding row (row_cnt[r]).
Increment the count of servers in the corresponding column (column_cnt[c]).

Count Connected Servers:

Iterate through the grid again:
If a cell contains a server (grid[r][c] == 1) and either:
The number of servers in the same row (row_cnt[r]) is greater than 1, or
The number of servers in the same column (column_cnt[c]) is greater than 1,
Increment a counter (res) to keep track of connected servers.

Return Result:

Return the res value, which represents the total number of servers connected to at least one other server.

Dry Run:

Let’s consider the following grid:

[[1,0],
 [1,1]]