Count Servers that Communicate

Problem Statement

In a given server center which can be visualized as a matrix (where each cell can either have a server denoted by 1 or nothing denoted by 0), two servers are considered to be able to communicate if they are positioned in the same row or the same column. The challenge posed is to determine how many servers are capable of such communication given this matrix setup. The end goal is to return the count of servers that are not isolated;

i.e., those that can communicate with at least one other server. This scenario is modeled by a m * n integer matrix referred to as grid.

Examples

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

Approach and Intuition

The task at hand involves identifying servers that are capable of "communicating" or connecting with one another based on their positioning within the same row or column. To approach this problem efficiently, it can be broken down into several clear steps:

1. Initialize Counters for Rows and Columns:

   • Initialize two arrays (or hash maps) to count servers in each row and in each column. Let these be rowCount[] and colCount[].

2. First Sweep - Count Servers:

   • Traverse the entire grid. For each cell containing a server (grid[i][j] == 1):
     • Increment the respective counters rowCount[i] and colCount[j].
     • This initial sweep allows us to record the total number of servers in each row and column.

3. Second Sweep - Identify Communicating Servers:

   • Traverse the grid a second time. For each server (grid[i][j] == 1), check the counters:
     • If rowCount[i] > 1 or colCount[j] > 1, it implies that this server is not isolated and can communicate with another server in its row or column.
     • Tally up such servers to get the total count of communicating servers.

The efficiency of this approach is supported by its O(m*n) time complexity, where m and n are the dimensions of the grid. This is because each server is processed twice: once for counting and once for verifying communication possibilities. This method ensures that even larger grids can be handled within a reasonable time frame.

By using row and column counters, the solution is both intuitive and efficient, allowing us to solve the problem with just two full scans of the grid. This approach takes full advantage of the constraints given, particularly the binary nature of the grid (only 0s and 1s) and the upper limit on grid dimensions (250x250).

Solutions

class Solution {
public:
    int serverCounter(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        int countCommServers = 0;
    
        for (int i = 0; i < row; ++i) {
            int serverCount in Row = 0;
            int firstServerCol = -1;
    
            // Finding servers in the current row
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j]) {
                    if (serverCountInRow == 0) {
                        firstServerCol = j;
                    }
                    serverCountInRow += 1;
                }
            }
    
            // Determine if servers in this row can communicate
            bool canTalk = (serverCountInRow > 1);
    
            // Checking for communication possibility for a lonely server
            if (!canTalk) {
                for (int k = 0; k < row; ++k) {
                    if (k != i && matrix[k][firstServerCol]) {
                        canTalk = true;
                        break;
                    }
                }
            }
    
            // Add to total if communication is possible
            if (canTalk) {
                countCommServers += serverCountInRow;
            }
        }
    
        return countCommServers;
    }
};