#1267

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Count Servers that Communicate

Count Servers that Communicate involves identifying servers in a grid that can communicate based on row or column connection.

array depth first search breadth first search union find matrix

Problem Statement

You are given a m * n integer matrix grid representing a server center. Each cell in the grid contains either a 1 (indicating a server) or a 0 (indicating no server). Two servers can communicate if they are in the same row or column, and you are asked to return the number of servers that can communicate with at least one other server.

For example, if a server is isolated, it cannot communicate with any other servers. Servers that are aligned in the same row or column can communicate with each other. The task is to determine how many servers in the given grid can communicate with at least one other server.

Examples

Example 1

Input: grid = [[1,0],[0,1]]

Output: 0

No servers can communicate with others.

Example 2

Input: grid = [[1,0],[1,1]]

Output: 3

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

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

Solution Approach

Count Servers in Rows and Columns

First, count the number of servers in each row and column. This allows us to determine which servers have at least one other server in the same row or column. Storing these counts in arrays for rows and columns provides a quick way to identify servers that can communicate.

Traverse the Grid

Next, traverse the grid cell by cell. For each server found (grid[i][j] == 1), check the corresponding row and column counts. If the count of servers in either the row or the column is greater than one, that server can communicate with another.

Efficient Counting with DFS or BFS

You can use Depth-First Search (DFS) or Breadth-First Search (BFS) to mark connected servers and avoid counting the same server multiple times. This ensures that only servers that are isolated or grouped together in their row or column are considered.

Complexity Analysis

Metric	Value
Time	O(m \times n)
Space	O(1)

The time complexity of this approach is O(m * n) because we need to traverse the grid and count the servers in each row and column. The space complexity is O(1), as we only need a few arrays for counting, independent of the grid size.

What Interviewers Usually Probe

Look for an efficient grid traversal approach, possibly utilizing row and column counters.
Check if the candidate correctly applies DFS or BFS to avoid redundant counts.
See if the candidate focuses on optimizing the traversal to avoid unnecessary recalculations.

Common Pitfalls or Variants

Common pitfalls

Not considering servers in isolated rows or columns which can't communicate with others.
Overcomplicating the solution by attempting to check each server pair individually instead of using row and column counts.
Failing to optimize the traversal, leading to unnecessary checks for already visited servers.

Follow-up variants

Grid with all cells having servers, where every server should communicate with every other server.
Grid with no servers, where the answer should be zero.
Sparse grids with servers scattered in isolated rows and columns.

FAQ

What is the key pattern to solve 'Count Servers that Communicate'?

The key pattern involves efficiently counting the number of servers in each row and column, then using that information to determine which servers can communicate.

How do I avoid counting the same server multiple times?

By using DFS or BFS, you can mark servers that have been visited, ensuring that each server is only counted once in its respective group.

Can I solve this problem without using DFS or BFS?

Yes, you can use an array-based approach to count servers in each row and column and directly compute the result without DFS or BFS.

How do row and column counts help in solving the problem?

Row and column counts allow you to quickly identify if a server has another server in the same row or column, making the traversal more efficient.

What happens if all servers are isolated?

If all servers are isolated, the output will be zero, as no server can communicate with any other server.

terminal

Solution

Solution 1: Counting

We can count the number of servers in each row and each column, then traverse each server. If the number of servers in the current server's row or column exceeds $1$, it means the current server meets the condition, and we increment the result by $1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        row = [0] * m
        col = [0] * n
        for i in range(m):
            for j in range(n):
                row[i] += grid[i][j]
                col[j] += grid[i][j]
        return sum(
            grid[i][j] and (row[i] > 1 or col[j] > 1)
            for i in range(m)
            for j in range(n)
        )

Continue Practicing

#1254 number of closed islands #1391 check if there is a valid path in a grid #1020 number of enclaves