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 than1
. 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:
-
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.
-
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. -
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.
-
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.