LeetCode 1267 - Count Servers that Communicate

The problem gives us a two dimensional grid representing a server center. Each cell contains either: - 1, meaning there

leetcodemediumarraydepth-first-searchbreadth-first-searchunion-findmatrixcounting

LeetCode Problem 1267

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix, Counting

Solution

Problem Understanding

The problem gives us a two dimensional grid representing a server center. Each cell contains either:

  • 1, meaning there is a server in that position
  • 0, meaning the cell is empty

A server can communicate with another server if both servers are located in the same row or the same column.

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

In other words, for every server in the grid, we need to determine whether there exists another server either:

  • somewhere else in the same row, or
  • somewhere else in the same column

If yes, that server should be included in the final count.

The output is a single integer representing the number of servers that are able to communicate.

The constraints are important:

  • 1 <= m, n <= 250
  • The grid size can therefore contain up to 250 * 250 = 62,500 cells

This is large enough that inefficient repeated scanning could become expensive, but small enough that linear or near linear matrix traversal is completely acceptable.

Several edge cases are important to consider:

  • A single isolated server should not be counted.
  • Entire rows or columns full of servers should count all servers in those rows or columns.
  • A server may communicate through either its row or its column. Only one connection is necessary.
  • A grid with no servers should return 0.
  • A grid where every server is isolated should also return 0.

For example:

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

Both servers are isolated because neither shares a row nor a column with another server, so the answer is 0.

By contrast:

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

All three servers communicate because:

  • the two servers in column 0 communicate
  • the two servers in row 1 communicate

So the answer is 3.

Approaches

Brute Force Approach

The most straightforward solution is to examine every server individually.

For each cell containing a server:

  1. Scan the entire row to see whether another server exists.
  2. Scan the entire column to see whether another server exists.
  3. If either scan finds another server, count the current server.

This approach is correct because it directly checks the definition of communication for every server.

However, it is inefficient.

Suppose the grid contains m * n cells. For every server, we may scan:

  • up to n cells in its row
  • up to m cells in its column

In the worst case, every cell contains a server, so the total complexity becomes:

O(m * n * (m + n))

With dimensions up to 250 x 250, this can become unnecessarily expensive.

Optimal Approach

The key observation is that communication depends only on how many servers exist in each row and each column.

A server communicates if:

row_count[row] > 1
OR
column_count[col] > 1

So instead of repeatedly scanning rows and columns for every server, we can preprocess:

  • how many servers exist in each row
  • how many servers exist in each column

Then we make a second pass through the grid and count servers whose row count or column count exceeds 1.

This avoids repeated work and reduces the complexity to linear traversal of the matrix.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * (m + n)) O(1) Repeatedly scans rows and columns for every server
Optimal O(m * n) O(m + n) Uses row and column frequency counting

Algorithm Walkthrough

Step 1: Create row and column count arrays

We create:

  • row_counts of size m
  • col_counts of size n

These arrays store how many servers appear in each row and column.

This preprocessing allows constant time communication checks later.

Step 2: Traverse the grid and populate counts

We iterate through every cell in the matrix.

Whenever we encounter a server (grid[r][c] == 1):

  • increment row_counts[r]
  • increment col_counts[c]

After this pass:

  • row_counts[r] tells us how many servers exist in row r
  • col_counts[c] tells us how many servers exist in column c

Step 3: Traverse the grid again

We now examine every server again.

For each server at position (r, c):

  • if row_counts[r] > 1, the server communicates
  • if col_counts[c] > 1, the server communicates

If either condition is true, we add the server to the answer.

Step 4: Return the total count

After processing all servers, the accumulated count is the final answer.

Why it works

The algorithm works because a server communicates if and only if another server exists in the same row or column.

The preprocessing step computes exactly this information:

  • rows with more than one server
  • columns with more than one server

During the second pass, every server is checked against these counts. Therefore, every communicating server is counted exactly once, and isolated servers are excluded.

Python Solution

from typing import List

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

        row_counts = [0] * rows
        col_counts = [0] * cols

        # Count servers in each row and column
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    row_counts[r] += 1
                    col_counts[c] += 1

        communicating_servers = 0

        # Count servers that can communicate
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    if row_counts[r] > 1 or col_counts[c] > 1:
                        communicating_servers += 1

        return communicating_servers

The implementation follows the algorithm directly.

First, we determine the matrix dimensions and initialize two counting arrays:

row_counts = [0] * rows
col_counts = [0] * cols

The first nested loop traverses the matrix and records how many servers exist in each row and column.

The second nested loop checks each server individually. A server contributes to the answer if:

row_counts[r] > 1 or col_counts[c] > 1

This condition exactly matches the communication rule from the problem statement.

Finally, the total number of communicating servers is returned.

Go Solution

func countServers(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])

    rowCounts := make([]int, rows)
    colCounts := make([]int, cols)

    // Count servers in each row and column
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 1 {
                rowCounts[r]++
                colCounts[c]++
            }
        }
    }

    communicatingServers := 0

    // Count communicating servers
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 1 {
                if rowCounts[r] > 1 || colCounts[c] > 1 {
                    communicatingServers++
                }
            }
        }
    }

    return communicatingServers
}

The Go implementation mirrors the Python solution closely.

Slices are used for rowCounts and colCounts, initialized using make.

Go does not require special handling for integer overflow here because the maximum number of servers is only 62,500, which easily fits within Go's int type.

The matrix is assumed to be non empty because the problem constraints guarantee at least one row and one column.

Worked Examples

Example 1

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

First Pass: Count Rows and Columns

Position Server? row_counts col_counts
(0,0) Yes [1,0] [1,0]
(0,1) No [1,0] [1,0]
(1,0) No [1,0] [1,0]
(1,1) Yes [1,1] [1,1]

Final counts:

row_counts = [1,1]
col_counts = [1,1]

Second Pass

Position Server? Communicates?
(0,0) Yes No
(1,1) Yes No

Result:

0

Example 2

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

First Pass

Position Server? row_counts col_counts
(0,0) Yes [1,0] [1,0]
(1,0) Yes [1,1] [2,0]
(1,1) Yes [1,2] [2,1]

Final counts:

row_counts = [1,2]
col_counts = [2,1]

Second Pass

Position row count col count Counted?
(0,0) 1 2 Yes
(1,0) 2 2 Yes
(1,1) 2 1 Yes

Result:

3

Example 3

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

First Pass

Final counts:

row_counts = [2,1,1,1]
col_counts = [1,1,2,1]

Second Pass

Position row count col count Counted?
(0,0) 2 1 Yes
(0,1) 2 1 Yes
(1,2) 1 2 Yes
(2,2) 1 2 Yes
(3,3) 1 1 No

Result:

4

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Two full traversals of the matrix
Space O(m + n) Row and column count arrays

The algorithm performs exactly two passes over the grid.

Each pass touches every cell once, so the total work is proportional to the number of cells in the matrix.

Additional memory is required only for:

  • one array of size m
  • one array of size n

Therefore, the extra space complexity is O(m + n).

Test Cases

solution = Solution()

# Example 1, isolated servers
assert solution.countServers([[1, 0], [0, 1]]) == 0

# Example 2, all servers communicate
assert solution.countServers([[1, 0], [1, 1]]) == 3

# Example 3, mixed communication
assert solution.countServers([
    [1, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1]
]) == 4

# Single cell with a server
assert solution.countServers([[1]]) == 0

# Single empty cell
assert solution.countServers([[0]]) == 0

# One row, all communicate
assert solution.countServers([[1, 1, 1, 1]]) == 4

# One column, all communicate
assert solution.countServers([[1], [1], [1]]) == 3

# Completely empty grid
assert solution.countServers([
    [0, 0],
    [0, 0]
]) == 0

# Multiple isolated servers
assert solution.countServers([
    [1, 0, 0],
    [0, 0, 1],
    [0, 1, 0]
]) == 0

# Mixed row and column communication
assert solution.countServers([
    [1, 0, 1],
    [0, 1, 0],
    [1, 0, 0]
]) == 4

# Large connected block
assert solution.countServers([
    [1, 1],
    [1, 1]
]) == 4
Test Why
[[1,0],[0,1]] Verifies isolated servers are excluded
[[1,0],[1,1]] Verifies row and column communication
Mixed 4x4 example Verifies selective counting
[[1]] Smallest possible server grid
[[0]] Smallest empty grid
Single row full of servers Tests row communication
Single column full of servers Tests column communication
Empty 2x2 grid Verifies no false positives
Diagonal isolated servers Tests isolated positions
Mixed connectivity grid Verifies combined row and column logic
Full 2x2 block Verifies dense communication

Edge Cases

Single Isolated Server

A grid like:

[[1]]

contains a server with no neighboring server in the same row or column.

A buggy implementation might incorrectly count any existing server. Our solution avoids this because both:

row_count = 1
col_count = 1

Neither exceeds 1, so the server is correctly excluded.

Servers Connected Only Through Columns

Consider:

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

The servers are not in the same row, but they do share a column.

A naive implementation focused only on rows would fail here. Our algorithm separately tracks row counts and column counts, so column communication is correctly detected.

Dense Grid of Servers

Consider:

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

Every server communicates with many others.

A brute force implementation repeatedly rescanning rows and columns would perform unnecessary work. Our counting approach handles this efficiently because each row and column count is computed only once.

Empty Grid Regions

A grid may contain many zero cells:

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

The algorithm must ignore empty cells entirely.

Our implementation checks:

if grid[r][c] == 1

before performing any communication logic, ensuring that empty cells never affect counts or results.