Count Servers that Communicate

Medium
300.

Count Servers that Communicate

Count Servers that Communicate is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon and Microsoft interviews.

You are given a map of a server centre as an m × n grid, where 1 marks a server and 0 marks an empty cell.

Two servers communicate if they sit in the same row or the same column. Return the number of servers that communicate with at least one other server.

Example 1

Input
grid = [[1,0],[0,1]]
Output
0
Explanation
The two servers share neither a row nor a column.

Example 2

Input
grid = [[1,0],[1,1]]
Output
3

Example 3

Input
grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output
4

Constraints

  • 1 <= grid.length, grid[i].length <= 8
  • grid[i][j] is 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var countServers = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Servers that Communicate — Problem & Solution

Count Servers that Communicate solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Servers that Communicate is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon and Microsoft interviews.

Problem statement

You are given a map of a server centre as an m × n grid, where 1 marks a server and 0 marks an empty cell.

Two servers communicate if they sit in the same row or the same column. Return the number of servers that communicate with at least one other server.

Example 1

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: The two servers share neither a row nor a column.

Example 2

Input: grid = [[1,0],[1,1]]
Output: 3

Example 3

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4

Constraints

  • 1 <= grid.length, grid[i].length <= 8
  • grid[i][j] is 0 or 1.

Hints for Count Servers that Communicate

  1. Hint 1

    No graph traversal is needed — a server is connected exactly when its row or its column holds another server.

  2. Hint 2

    One pass tallies the servers per row and per column.

  3. Hint 3

    A second pass counts every server whose row count or column count exceeds one.

How to solve Count Servers that Communicate

A server communicates iff its row or its column holds another server, so per-row and per-column tallies decide every cell without a traversal.

Approach

  1. Compute rowCount and colCount.
  2. Count servers where rowCount[r] > 1 or colCount[c] > 1.

Why it works

"At least one other server in the same row or column" is exactly the tally condition; no transitivity is involved.

Complexity

  • Time — O(m · n)
  • Space — O(m + n)

Pitfalls

  • Do not model this as connected components — the question asks about direct communication only.

Reference solution

Python

def countServers(grid) -> int:
    m, n = len(grid), len(grid[0])
    row_count = [sum(row) for row in grid]
    col_count = [sum(grid[r][c] for r in range(m)) for c in range(n)]
    return sum(1 for r in range(m) for c in range(n)
               if grid[r][c] == 1 and (row_count[r] > 1 or col_count[c] > 1))

Java

public static int countServers(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] rowCount = new int[m];
    int[] colCount = new int[n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                rowCount[r]++;
                colCount[c]++;
            }
        }
    }
    int total = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1 && (rowCount[r] > 1 || colCount[c] > 1)) total++;
        }
    }
    return total;
}

C++

int countServers(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<int> rowCount(m, 0), colCount(n, 0);
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                rowCount[r]++;
                colCount[c]++;
            }
        }
    }
    int total = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1 && (rowCount[r] > 1 || colCount[c] > 1)) total++;
        }
    }
    return total;
}

JavaScript

var countServers = function(grid) {
    const m = grid.length, n = grid[0].length;
    const rowCount = new Array(m).fill(0);
    const colCount = new Array(n).fill(0);
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) {
                rowCount[r]++;
                colCount[c]++;
            }
        }
    }
    let total = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1 && (rowCount[r] > 1 || colCount[c] > 1)) total++;
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)