Approach: Row/column counts

count servers per row and column; a server communicates if its row or column has more than one server

Complexity: O(m*n) time, O(m+n) space.

Full Solution — all languages

class Solution:
    def countServers(self, grid):
        R, C = len(grid), len(grid[0])
        rowC = [0] * R
        colC = [0] * C
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 1:
                    rowC[r] += 1
                    colC[c] += 1
        cnt = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 1 and (rowC[r] > 1 or colC[c] > 1):
                    cnt += 1
        return cnt

import java.util.*;
class Solution {
    public int countServers(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        int[] rowC = new int[R], colC = new int[C];
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 1) {
            rowC[r]++;
            colC[c]++;
        }
        int cnt = 0;
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 1 && (rowC[r] > 1 || colC[c] > 1)) cnt++;
        return cnt;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int countServers(vector<vector<int>>& grid) {
        int R = grid.size(), C = grid[0].size();
        vector<int> rowC(R, 0), colC(C, 0);
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 1) {
            rowC[r]++;
            colC[c]++;
        }
        int cnt = 0;
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 1 && (rowC[r] > 1 || colC[c] > 1)) cnt++;
        return cnt;
    }
};

/**
 * @param {number[][]} grid
 * @return {number}
 */ var countServers = function(grid) {
    const R = grid.length, C = grid[0].length;
    const rowC = new Array(R).fill(0), colC = new Array(C).fill(0);
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (grid[r][c] === 1) {
        rowC[r]++;
        colC[c]++;
    }
    let cnt = 0;
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (grid[r][c] === 1 && (rowC[r] > 1 || colC[c] > 1)) cnt++;
    return cnt;
};

Count Servers that Communicate

Example 1

Example 2

Constraints