Count Servers that Communicate

Medium · Graphs · Explanation and code example

Iteration (Space Optimized)

How it works

We can avoid using extra arrays by processing rows and columns separately and using the grid itself to mark processed servers. First, we process all rows with multiple servers and mark those servers. Then, we process columns and only count unmarked servers in columns with multiple servers. The marking prevents double counting servers that belong to both a communicating row and column.

Steps

  1. Process rows first:
    • For each row with more than one server, add all servers in that row to the result.
    • Mark these servers by setting their value to -1.
  2. Process columns:
    • For each column, count total servers (using absolute values) and unmarked servers.
    • If the column has two or more servers, add the count of unmarked servers to the result.
    • Restore marked servers by setting -1 back to 1.
  3. Return the total count.

Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(1)

Where m is the number of rows and n is the number of columns of the given matrix grid.

Things to watch for

Counting Total Servers Instead of Communicating Servers

A server only counts if it can communicate with at least one other server. Counting all servers (all cells with value 1) ignores the communication requirement.

Using OR Instead of Checking Both Row and Column Counts

A server communicates if its row has 2+ servers OR its column has 2+ servers. Using AND would incorrectly require both conditions.

Double Counting Servers

When processing rows and columns separately (in the space-optimized solution), servers that are in both a communicating row and a communicating column can be counted twice. Mark processed servers to avoid this.

Python code example

from typing import List

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        res = 0
        ROWS, COLS = len(grid), len(grid[0])

        # Rows
        for r in range(ROWS):
            row_sum = sum(grid[r])
            if row_sum <= 1:
                continue
            res += row_sum
            for c in range(COLS):
                if grid[r][c]:
                    grid[r][c] = -1  # Mark

        # Cols
        for c in range(COLS):
            col_sum = unmarked = 0
            for r in range(ROWS):
                col_sum += abs(grid[r][c])
                if grid[r][c] > 0:
                    unmarked += 1
                elif grid[r][c] < 0:
                    grid[r][c] = 1 # Unmark
            if col_sum >= 2:
                res += unmarked

        return res

C++ code example

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int res = 0;
        int ROWS = grid.size(), COLS = grid[0].size();

        // Rows
        for (int r = 0; r < ROWS; r++) {
            int rowSum = accumulate(grid[r].begin(), grid[r].end(), 0);
            if (rowSum <= 1) continue;
            res += rowSum;
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 1) grid[r][c] = -1; // Mark
            }
        }

        // Cols
        for (int c = 0; c < COLS; c++) {
            int colSum = 0, unmarked = 0;
            for (int r = 0; r < ROWS; r++) {
                colSum += abs(grid[r][c]);
                if (grid[r][c] > 0) unmarked++;
                else if (grid[r][c] < 0) grid[r][c] = 1; // Unmark
            }
            if (colSum >= 2) res += unmarked;
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations