Leetcode 1267. Count Servers that Communicate

Problem Description

In this problem, we have a server center represented as a matrix where 1 indicates the presence of a server and 0 indicates the absence of a server. If two servers are in the same row or column, they can communicate with each other. We are asked to return the number of servers that can communicate with any other server.

For example, consider the following grid:

1
2
31 0
40 1

In this scenario, each server is isolated and cannot communicate with any other server. Hence, the output is 0.

Problem Solution

The solution to this problem involves two steps:

• Firstly, we iterate through the grid and count the number of servers in each row and each column.
• Then, we again iterate through the grid and for each cell containing a server (1), we check if the count of servers in its row or column is greater than 1. If it is, this means the server can communicate with at least one other server. We increment a counter in this case.
• Finally, this counter gives us the number of servers that can communicate with at least one other server.

Python Solution

1
2python
3class Solution:
4    def countServers(self, grid: List[List[int]]) -> int:
5        rows, cols = [0]*len(grid), [0]*len(grid[0])
6
7        for i in range(len(grid)):
8            for j in range(len(grid[0])):
9                if grid[i][j] == 1:
10                    rows[i] += 1
11                    cols[j] += 1
12
13        ans = 0
14        for i in range(len(grid)):
15            for j in range(len(grid[0])):
16                if grid[i][j] == 1 and (rows[i] > 1 or cols[j] > 1):
17                    ans += 1
18
19        return ans

Java Solution

1
2java
3class Solution {
4    public int countServers(int[][] grid) {
5        int m = grid.length, n = grid[0].length;
6        int[] rows = new int[m], cols = new int[n];
7        int res = 0;
8
9        for(int i = 0; i < m; i++) {
10            for(int j = 0; j < n; j++) {
11                if(grid[i][j] == 1) {
12                    rows[i]++;
13                    cols[j]++;
14                }
15            }
16        }
17
18        for(int i = 0; i < m; i++) {
19            for(int j = 0; j < n; j++) {
20                if(grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
21                    res++;
22                }
23            }
24        }
25
26        return res;
27    }
28}

JavaScript Solution

1
2javascript
3var countServers = function(grid) {
4    let m = grid.length, n = grid[0].length;
5    let rows = Array(m).fill(0), cols = Array(n).fill(0);
6    let res = 0;
7
8    for(let i = 0; i < m; i++) {
9        for(let j = 0; j < n; j++) {
10            if(grid[i][j] === 1) {
11                rows[i]++;
12                cols[j]++;
13            }
14        }
15    }
16
17    for(let i = 0; i < m; i++) {
18        for(let j = 0; j < n; j++) {
19            if(grid[i][j] === 1 && (rows[i] > 1 || cols[j] > 1)) {
20                res++;
21            }
22        }
23    }
24
25    return res;
26};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int countServers(vector<vector<int>>& grid) {
6        int m = grid.size(), n = grid[0].size();
7        vector<int> rows(m, 0), cols(n, 0);
8        int res = 0;
9
10        for(int i = 0; i < m; i++) {
11            for(int j = 0; j < n; j++) {
12                if(grid[i][j] == 1) {
13                    rows[i]++;
14                    cols[j]++;
15                }
16            }
17        }
18
19        for(int i = 0; i < m; i++) {
20            for(int j = 0; j < n; j++) {
21                if(grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
22                    res++;
23                }
24            }
25        }
26
27        return res;
28    }
29};

C# Solution

1
2csharp
3public class Solution {
4    public int CountServers(int[][] grid) {
5        int m = grid.Length, n = grid[0].Length;
6        int[] rows = new int[m], cols = new int[n];
7        int res = 0;
8
9        for(int i = 0; i < m; i++) {
10            for(int j = 0; j < n; j++) {
11                if(grid[i][j] == 1) {
12                    rows[i]++;
13                    cols[j]++;
14                }
15            }
16        }
17
18        for(int i = 0; i < m; i++) {
19            for(int j = 0; j < n; j++) {
20                if(grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
21                    res++;
22                }
23            }
24        }
25
26        return res;
27    }
28}

Explanation

The above provided solutions in Python, Java, JavaScript, C++, and C# all follow the same logic. Here is the step-by-step explanation of the logic:

1. Initialize server count array for row and column: For every row and column, an array is initialized to zero to keep track of the numbers of servers in the row and column respectively.

2. Count the servers: Iterate through every cell in the grid. If a cell contains a server (1), increment the corresponding row and column count in the row and column array.

3. Count the communicating servers: Iterate through every cell in the grid again. If a cell contains a server and the number of servers in its row or column is greater than one, that server can communicate with at least one server. Hence, increment the result with the number of communicating servers.

4. Return the number of communicating servers: Finally, return the result which contains the number of servers that can communicate with at least one other server.

Time Complexity

The time complexity of this solution is O(n * m), where n and m are the number of rows and columns of the grid respectively. This is because we need to iterate through each cell in the grid twice.

Space Complexity

The space complexity of this solution is O(n + m), where n and m are the number of rows and columns of the grid respectively. This is because we are storing the number of servers in each row and each column in two separate arrays.