Scale Engineer

Count Servers that Communicate

Med
#1182Time: O(m * n). The algorithm involves two separate passes over the grid, each taking O(m * n) time. The total time complexity is therefore O(m * n).Space: O(m + n), for the two arrays used to store the server counts for each row and column.
Patterns
Counting
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
ArrayMatrix

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This efficient approach avoids redundant work by first counting the number of servers in each row and column in a single pass. In a second pass, it determines which servers communicate based on these pre-calculated counts.

Algorithm

  1. Get the dimensions of the grid, m (rows) and n (columns).
  2. Create an integer array rowCount of size m, initialized to zeros.
  3. Create an integer array colCount of size n, initialized to zeros.
  4. First Pass (Count servers): a. Iterate through each cell (i, j) of the grid. b. If grid[i][j] == 1, increment rowCount[i] and colCount[j].
  5. Initialize communicatingCount = 0.
  6. Second Pass (Identify communicating servers): a. Iterate through each cell (i, j) of the grid. b. If grid[i][j] == 1 and (rowCount[i] > 1 or colCount[j] > 1), increment communicatingCount.
  7. Return communicatingCount.

Walkthrough

The core idea is that a server at (i, j) communicates if and only if there is at least one other server in its row or its column. This is equivalent to saying the total number of servers in its row is greater than 1, or the total number of servers in its column is greater than 1. The algorithm uses two auxiliary arrays, rowCount and colCount, to store the server counts for each row and column, respectively.

First Pass: The grid is traversed once to populate rowCount and colCount. For each cell (i, j) containing a server, rowCount[i] and colCount[j] are incremented.

Second Pass: The grid is traversed again. For each cell (i, j) containing a server, we check if rowCount[i] > 1 or colCount[j] > 1. If this condition holds, the server communicates, and a counter is incremented. Finally, the total count of communicating servers is returned.

class Solution {    public int countServers(int[][] grid) {        if (grid == null || grid.length == 0 || grid[0].length == 0) {            return 0;        }        int m = grid.length;        int n = grid[0].length;        int[] rowCount = new int[m];        int[] colCount = new int[n];         // First pass: count servers in each row and column        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1) {                    rowCount[i]++;                    colCount[j]++;                }            }        }         int communicatingCount = 0;        // Second pass: count servers that can communicate        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1) {                    // A server communicates if there is at least one other server in its row or column                    if (rowCount[i] > 1 || colCount[j] > 1) {                        communicatingCount++;                    }                }            }        }        return communicatingCount;    }}

Complexity

Time

O(m * n). The algorithm involves two separate passes over the grid, each taking O(m * n) time. The total time complexity is therefore O(m * n).

Space

O(m + n), for the two arrays used to store the server counts for each row and column.

Trade-offs

Pros

  • Optimal time complexity, as it only requires two passes over the grid.

  • Significantly faster than the brute-force approach for larger grids.

  • The logic is straightforward and easy to follow.

Cons

  • Requires extra space for the count arrays, which could be a concern for extremely large grids (though acceptable for the given constraints).

Solutions

class Solution {public  int countServers(int[][] grid) {    int m = grid.length, n = grid[0].length;    int[] row = new int[m];    int[] col = new int[n];    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 1) {          row[i]++;          col[j]++;        }      }    }    int ans = 0;    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 1 && (row[i] > 1 || col[j] > 1)) {          ++ans;        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem