x## 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.

Examples

Example 1:

$$ \begin{array}{c|c} \colorbox{red} C & \\ \hline & \colorbox{red} C \\ \end{array} $$

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

Example 2:

$$ \begin{array}{c|c} \colorbox{blue} C & \\ \hline \colorbox{blue} C & \colorbox{blue} C \\ \end{array} $$

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

Example 3:

$$ \begin{array}{c|c|c|c} \colorbox{blue} C & \colorbox{blue} C & & \\ \hline & & \colorbox{blue} C & \\ \hline & & \colorbox{blue} C & \\ \hline & & & \colorbox{red} C & \\ \end{array} $$

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

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

In this approach, we check for each server whether there is another server in its row or column manually. This means for each server, we traverse its entire row and column to check for another server.

Here are the steps:

  1. Iterate through every cell in the grid.
  2. If a cell has a server (1), check its entire row and column to see if there is at least one more server (1).
  3. If such a server is found, mark the current server as communicating.

Complexity

  • ⏰ Time complexity: O((m * n) * (m + n)) due to nested loops and checking rows and columns for each server.
  • 🧺 Space complexity: O(1)

Method 2 - Count server in each row and column using vectors

We need to count servers that can communicate with at least one other server, and servers communicate if they share the same row or column. Here is the approach:

  • First, count the number of servers in each row and column.
  • Then, iterate through the grid once more and count the servers that have more than one server either in the same row or the same column.

Code

Java
class Solution {
    public int countServers(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] rowCounts = new int[m];
        int[] colCounts = new int[n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowCounts[i]++;
                    colCounts[j]++;
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && (rowCounts[i] > 1 || colCounts[j] > 1)) {
                    ans++;
                }
            }
        }
        
        return ans;
    }
}
Python
class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        m: int = len(grid)
        n: int = len(grid[0])
        row_counts: List[int] = [0] * m
        col_counts: List[int] = [0] * n
        
        # Count servers in each row and column
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    row_counts[i] += 1
                    col_counts[j] += 1
        
        # Count servers that can communicate
        ans: int = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and (row_counts[i] > 1 or col_counts[j] > 1):
                    ans += 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(m * n) where m is the number of rows and n is the number of columns since we iterate over the entire grid twice.
  • 🧺 Space complexity: O(m + n) for storing the counts of servers in rows and columns.