Problem Description

You have a grid representing a server center layout, given as an m × n matrix where:

• 1 indicates a server is present at that cell
• 0 indicates no server at that cell

Two servers can communicate with each other if they are located either:

• In the same row, OR
• In the same column

Your task is to count how many servers can communicate with at least one other server.

For example, if a server is alone in its row AND alone in its column, it cannot communicate with any other server. But if a server shares its row or column with at least one other server, it can communicate and should be counted in the result.

The solution works by:

1. First counting how many servers exist in each row and each column using arrays row and col
2. Then checking each server position - if that server's row has more than 1 server (row[i] > 1) OR its column has more than 1 server (col[j] > 1), it means this server can communicate with others
3. The final count gives us the total number of servers that can communicate with at least one other server

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: We can model this as a graph problem where servers are nodes, and servers that can communicate (same row or column) have edges between them.

Is it a tree?

• No: The communication pattern between servers doesn't form a tree structure. Servers can form cycles (e.g., servers forming a rectangle pattern would create cycles).

Is the problem related to directed acyclic graphs?

• No: The communication between servers is bidirectional (if server A can communicate with server B, then B can also communicate with A), and cycles can exist.

Is the problem related to shortest paths?

• No: We're not looking for shortest paths between servers; we're counting servers that have at least one communication partner.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - we need to find servers that are connected to at least one other server through row or column relationships.

Disjoint Set Union

• This would be one valid approach, where we could union servers that can communicate and then count servers in components of size > 1.

However, looking at the actual solution provided, it uses a simpler counting approach rather than DFS. But if we were to solve it with DFS:

Alternative DFS approach: We could treat each server as a node and use DFS to explore all servers in the same row or column, marking them as part of the same connected component. Then count all servers that belong to components with more than one server.

Conclusion: While the flowchart suggests DSU for connectivity problems, and DFS could also work by exploring connected components, the actual optimal solution uses a counting approach that's even more efficient than graph traversal methods.

Intuition

When we think about which servers can communicate, we need to identify servers that aren't isolated. A server is isolated only when it's the sole server in both its row AND its column.

The key insight is that we don't need to explicitly build connections between servers or explore graph components. Instead, we can use a counting strategy: if we know how many servers exist in each row and each column, we can quickly determine if any given server can communicate.

Think of it this way: for a server at position (i, j) to communicate with others, at least one of these conditions must be true:

• There's another server in row i (meaning row[i] > 1)
• There's another server in column j (meaning col[j] > 1)

This leads us to a two-pass approach:

1. First pass: Count how many servers are in each row and column. This gives us the "communication potential" for each position.
2. Second pass: For each server, check if it has communication potential (either its row count or column count is greater than 1).

Why is this better than DFS or DSU? While those approaches would work by finding connected components, they're overkill for this problem. We don't need to know which specific servers communicate with each other or track component sizes - we just need to know if a server has ANY communication partner. The counting approach directly answers this question in O(m*n) time with just two passes through the grid.

The elegance lies in transforming what seems like a connectivity problem into a simple counting problem, avoiding the complexity of graph traversal altogether.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The implementation follows the counting strategy we identified in our intuition. Let's walk through the code step by step:

Step 1: Initialize counters for rows and columns

m, n = len(grid), len(grid[0])
row = [0] * m
col = [0] * n

We create two arrays:

• row[i] will store the count of servers in row i
• col[j] will store the count of servers in column j

Step 2: First pass - Count servers in each row and column

for i in range(m):
    for j in range(n):
        if grid[i][j]:
            row[i] += 1
            col[j] += 1

We traverse the entire grid once. Whenever we encounter a server (grid[i][j] == 1), we increment both:

• The counter for its row (row[i])
• The counter for its column (col[j])

After this pass, we know exactly how many servers exist in each row and column.

Step 3: Second pass - Count communicating servers

return sum(
    grid[i][j] and (row[i] > 1 or col[j] > 1)
    for i in range(m)
    for j in range(n)
)

We traverse the grid again, but this time we count servers that can communicate. For each position (i, j):

• First check if there's a server at this position (grid[i][j])
• If yes, check if it can communicate: either row[i] > 1 (has row neighbors) or col[j] > 1 (has column neighbors)
• The expression evaluates to True (counted as 1) if both conditions are met, False (counted as 0) otherwise

The sum() function with a generator expression efficiently counts all True values, giving us the total number of servers that can communicate.

Time Complexity: O(m × n) - we traverse the grid twice
Space Complexity: O(m + n) - for storing row and column counts

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×4 grid:

grid = [[1, 0, 0, 1],
        [0, 0, 1, 0],
        [1, 1, 0, 0]]

Step 1: Initialize counters

row = [0, 0, 0]  # for 3 rows
col = [0, 0, 0, 0]  # for 4 columns

Step 2: First pass - Count servers in each row and column

We traverse each cell and count servers:

• Position (0,0): Server found! → row[0] = 1, col[0] = 1
• Position (0,3): Server found! → row[0] = 2, col[3] = 1
• Position (1,2): Server found! → row[1] = 1, col[2] = 1
• Position (2,0): Server found! → row[2] = 1, col[0] = 2
• Position (2,1): Server found! → row[2] = 2, col[1] = 1

After the first pass:

row = [2, 1, 2]  # Row 0 has 2 servers, Row 1 has 1, Row 2 has 2
col = [2, 1, 1, 1]  # Col 0 has 2 servers, others have 1 each

Step 3: Second pass - Count communicating servers

Now we check each server to see if it can communicate:

• Server at (0,0): row[0] = 2 > 1 ✓ (has row neighbor) → Count it!
• Server at (0,3): row[0] = 2 > 1 ✓ (has row neighbor) → Count it!
• Server at (1,2): row[1] = 1 and col[2] = 1 ✗ (isolated) → Don't count
• Server at (2,0): col[0] = 2 > 1 ✓ (has column neighbor) → Count it!
• Server at (2,1): row[2] = 2 > 1 ✓ (has row neighbor) → Count it!

Result: 4 servers can communicate

The servers at positions (0,0), (0,3), (2,0), and (2,1) can all communicate with at least one other server. The server at (1,2) is isolated (alone in both its row and column) and cannot communicate.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of two main passes through the grid:

1. First pass: Iterates through all m × n cells to count servers in each row and column, taking O(m × n) time.
2. Second pass: Iterates through all m × n cells again to count servers that can communicate (those in rows or columns with more than one server), taking O(m × n) time.

Total time complexity: O(m × n) + O(m × n) = O(m × n)

Space Complexity: O(m + n)

The algorithm uses additional space for:

• row array of size m to store the count of servers in each row: O(m)
• col array of size n to store the count of servers in each column: O(n)

Total space complexity: O(m) + O(n) = O(m + n)

Where m and n are the number of rows and columns in the matrix, respectively.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Counting Total Servers Instead of Communicating Servers

A frequent mistake is counting all servers in rows or columns with multiple servers, rather than counting individual servers that can communicate.

Incorrect approach:

# Wrong: This counts rows and columns, not individual servers
result = 0
for i in range(rows):
    if row_counts[i] > 1:
        result += row_counts[i]  # This double counts servers!

Why it's wrong: If you have 3 servers in a row and 2 of them are also in columns with other servers, you'd count those servers multiple times.

Correct approach:

# Right: Check each server individually
for i in range(rows):
    for j in range(cols):
        if grid[i][j] == 1 and (row_counts[i] > 1 or col_counts[j] > 1):
            connected_servers += 1

Pitfall 2: Misunderstanding the Communication Condition

Another common error is thinking servers need other servers in BOTH the same row AND column to communicate.

Incorrect logic:

# Wrong: Using AND instead of OR
if grid[i][j] == 1 and row_counts[i] > 1 and col_counts[j] > 1:
    connected_servers += 1

Correct logic:

# Right: A server can communicate if it has neighbors in row OR column
if grid[i][j] == 1 and (row_counts[i] > 1 or col_counts[j] > 1):
    connected_servers += 1

Pitfall 3: Off-by-One Errors in Counting

Some implementations mistakenly check for >= 1 instead of > 1 when determining if a server can communicate.

Incorrect check:

# Wrong: This would count isolated servers too
if grid[i][j] == 1 and (row_counts[i] >= 1 or col_counts[j] >= 1):
    connected_servers += 1

Why it's wrong: row_counts[i] >= 1 is always true for any server, since the server itself contributes 1 to the count. We need > 1 to ensure there's at least one OTHER server.

Correct check:

# Right: Ensures at least 2 servers in row or column
if grid[i][j] == 1 and (row_counts[i] > 1 or col_counts[j] > 1):
    connected_servers += 1