Code Implementation

class Solution:
    def countServers(self, grid):
        from collections import Counter
        rows = len(grid)
        cols = len(grid[0])
        row_count = Counter()
        col_count = Counter()
        
        # Count servers in each row and column
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    row_count[r] += 1
                    col_count[c] += 1
        
        # Count servers that can communicate
        result = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    if row_count[r] > 1 or col_count[c] > 1:
                        result += 1
        return result
      

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        vector<int> row_count(rows, 0), col_count(cols, 0);
        // Count servers in each row and column
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 1) {
                    row_count[r]++;
                    col_count[c]++;
                }
            }
        }
        // Count servers that can communicate
        int result = 0;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 1) {
                    if (row_count[r] > 1 || col_count[c] > 1) {
                        result++;
                    }
                }
            }
        }
        return result;
    }
};
      

class Solution {
    public int countServers(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[] rowCount = new int[rows];
        int[] colCount = new int[cols];
        // Count servers in each row and column
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    rowCount[r]++;
                    colCount[c]++;
                }
            }
        }
        // Count servers that can communicate
        int result = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    if (rowCount[r] > 1 || colCount[c] > 1) {
                        result++;
                    }
                }
            }
        }
        return result;
    }
}
      

var countServers = function(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    const rowCount = new Array(rows).fill(0);
    const colCount = new Array(cols).fill(0);
    // Count servers in each row and column
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 1) {
                rowCount[r]++;
                colCount[c]++;
            }
        }
    }
    // Count servers that can communicate
    let result = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 1) {
                if (rowCount[r] > 1 || colCount[c] > 1) {
                    result++;
                }
            }
        }
    }
    return result;
};
      

Problem Description

You are given a 2D grid representing a network of servers. Each cell in the grid contains either a 1 (representing a server) or a 0 (representing an empty space). Two servers can communicate if they are located on the same row or the same column. Your task is to count the number of servers that can communicate with at least one other server (either in their row or column).

• Each server may only communicate if there is another server in the same row or column.
• Do not count isolated servers (servers with no other servers in their row or column).
• There is always at least one row and one column.
• The grid size can be up to 250 x 250.

Thought Process

At first glance, you might think to check for each server whether there is another server in its row or column. This could be done by scanning the row and column for every server found, but that would result in a lot of repeated work, especially for large grids.

A brute-force approach would involve, for every server, scanning its row and column to see if there is another server. However, this would be inefficient, potentially taking O(N * M * (N + M)), where N and M are the number of rows and columns.

To optimize, notice that what matters for each cell is just how many servers are in its row and column. If a row or column has more than one server, then all servers in that row or column can communicate with at least one other server. So, we can first count the number of servers in each row and column, and then for each server, check if its row or column has more than one server.

Solution Approach

To solve this efficiently, we use the following steps:

1. Count servers in each row and column:
   • Initialize two arrays (or hash maps): one for counting servers in each row, and one for each column.
   • Iterate through the grid. For every cell containing a 1, increment the count for that row and column.
2. Identify servers that can communicate:
   • Iterate through the grid again. For each server, check if its row or column count is greater than 1.
   • If so, it means there is at least one other server in the same row or column, so this server can communicate.
   • Increment a result counter for each such server.
3. Return the result:
   • The result counter holds the total number of servers that can communicate with at least one other server.

This method avoids repeated scanning by leveraging the counts, making the solution much more efficient.

Example Walkthrough

Let's walk through an example:

Input grid:
[[1, 0],
 [1, 1]]
  

1. First pass: count servers in each row and column
   • Row 0: 1 server (at [0,0])
   • Row 1: 2 servers (at [1,0] and [1,1])
   • Column 0: 2 servers (at [0,0] and [1,0])
   • Column 1: 1 server (at [1,1])
2. Second pass: check each server
   • [0,0]: row count = 1, col count = 2 ⇒ communicates (col count > 1)
   • [1,0]: row count = 2, col count = 2 ⇒ communicates (both > 1)
   • [1,1]: row count = 2, col count = 1 ⇒ communicates (row count > 1)
3. Result: All 3 servers can communicate.

Time and Space Complexity

• Brute-force approach:
  • For each server, scan its entire row and column to see if another server exists.
  • Time complexity: O(N * M * (N + M)), where N is rows and M is columns.
  • Space complexity: O(1) extra space (not counting input).
• Optimized approach (as described above):
  • First pass: O(N * M) to count servers in each row and column.
  • Second pass: O(N * M) to check each server's row and column counts.
  • Total time complexity: O(N * M).
  • Space complexity: O(N + M) for row and column counts.

The optimized approach is much more efficient and can handle large grids within time limits.

Summary

The key insight is that servers can communicate if their row or column contains more than one server. By counting servers in each row and column, we can efficiently determine which servers can communicate, avoiding redundant checks. This leads to a solution with linear time complexity relative to the grid size, making it both elegant and practical for large inputs.