Count Servers that Communicate

MEDIUM

Description

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

Checkout 2 different approaches to solve Count Servers that Communicate. Click on different approaches to view the approach and algorithm in detail.

Two-Pass Counting

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

Get the dimensions of the grid, m (rows) and n (columns).
Create an integer array rowCount of size m, initialized to zeros.
Create an integer array colCount of size n, initialized to zeros.
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].
Initialize communicatingCount = 0.
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.
Return communicatingCount.

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 Analysis

Time Complexity: 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 Complexity: O(m + n), for the two arrays used to store the server counts for each row and column.

Pros and Cons

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).

Code Solutions

Checking out 3 solutions in different languages for Count Servers that Communicate. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Count Servers that Communicate

Algorithms:

Depth-First SearchBreadth-First SearchUnion Find

Patterns:

Counting

Data Structures:

ArrayMatrix