# Count Servers that Communicate
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-servers-that-communicate)
Canonical: https://scaleengineer.com/dsa/problems/count-servers-that-communicate
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-servers-that-communicate/image0.jpg)

**Input:** grid = [[1,0],[0,1]]
**Output:** 0
**Explanation:** No servers can communicate with others.

**Example 2:**

**![](https://assets.glich.co/dsa/count-servers-that-communicate/image1.jpg)**

**Input:** grid = [[1,0],[1,1]]
**Output:** 3
**Explanation:** All three servers can communicate with at least one other server.

**Example 3:**

![](https://assets.glich.co/dsa/count-servers-that-communicate/image2.jpg)

**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
## Brute Force Iteration
This approach iterates through every cell of the grid. For each cell that contains a server, it performs another scan of the entire corresponding row and column to check for the presence of at least one other server.
**Time:** O(m * n * (m + n)). For each of the `m*n` cells, we might scan a full row (of length `n`) and a full column (of length `m`). · **Space:** O(1), as it only uses a few variables to keep track of counts and flags, not dependent on the grid size.
**Pros:** Simple to conceptualize and implement.; Very low space complexity as it doesn't use any extra data structures proportional to the input size.
**Cons:** Highly inefficient time complexity, which may lead to a 'Time Limit Exceeded' error on larger grids.; Performs a lot of redundant work by repeatedly scanning the same rows and columns.
### Explanation
The algorithm initializes a counter for communicating servers to zero. It then traverses the grid using nested loops. When a server is found at `grid[i][j]`, a flag `isCommunicating` is set to `false`. Two more loops are started: one to scan the `i`-th row and another to scan the `j`-th column. During these scans, if another server is found (i.e., `grid[i][k] == 1` where `k != j`, or `grid[k][j] == 1` where `k != i`), the `isCommunicating` flag is set to `true`, and the inner scans are terminated early (using `break`). If, after checking both the row and column, the `isCommunicating` flag is `true`, the main counter is incremented. This process is repeated for every server in the grid.

```java
class Solution {
    public int countServers(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int communicatingCount = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    boolean foundOtherServer = false;
                    // Check row for other servers
                    for (int k = 0; k < n; k++) {
                        if (k != j && grid[i][k] == 1) {
                            foundOtherServer = true;
                            break;
                        }
                    }
                    if (foundOtherServer) {
                        communicatingCount++;
                        continue; // Already counted, move to the next server
                    }
                    // Check column for other servers
                    for (int k = 0; k < m; k++) {
                        if (k != i && grid[k][j] == 1) {
                            foundOtherServer = true;
                            break;
                        }
                    }
                    if (foundOtherServer) {
                        communicatingCount++;
                    }
                }
            }
        }
        return communicatingCount;
    }
}
```
### Algorithm
1. Initialize `communicatingCount = 0`.
2. Get the dimensions of the grid, `m` (rows) and `n` (columns).
3. Iterate through each cell `(i, j)` from `(0, 0)` to `(m-1, n-1)`.
4. If `grid[i][j] == 1`:
    a. Initialize a boolean flag `foundOtherServer = false`.
    b. **Check the row:** Iterate `k` from `0` to `n-1`. If `k != j` and `grid[i][k] == 1`, set `foundOtherServer = true` and break.
    c. **Check the column:** If `foundOtherServer` is still false, iterate `k` from `0` to `m-1`. If `k != i` and `grid[k][j] == 1`, set `foundOtherServer = true` and break.
    d. If `foundOtherServer` is true, increment `communicatingCount`.
5. Return `communicatingCount`.

## 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.
**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.
**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).
### Explanation
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.

```java
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;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

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

```

### Python

```python
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): if grid[i][j]: row[i] += 1 col[j] += 1 return sum(grid[i][j] and (row[i] > 1 or col[j] > 1) for i in range(m) for j in range(n))

```