1267: Count-Servers-that-Communicate
Medium
table of contents
Intuitively speaking, since there is a maximum of
min(m, n) servers that do not
communicate with each other in the m x n grid and the
conditions for this to occur are so restrictive
(no other server in the same row or column), it should
be easier to calculate this than the number of
servers that do communicate with another server.
From now on, we will be calling the servers that do not
communicate with another server,
social-distancing servers.
The first part of every solution should be the same; to iterate
through the m x n grid to gather information, meaning
our algorithm should have a minimum time complexity of
O(m x n) already.1 To find the number of
social-distancing servers, since they have to be the sole
server in their respective row and column, it makes sense to keep
track of row_count or col_count (number
of servers in each row / column respectively).
I decided to keep track of col_count (number of servers
in each column) and create a set of all the rows with only 1 element
during my traversal through the m x n grid, as this means
that it takes O(1) time to determine if a server is
social-distancing or not, meaning to determine the number
of servers that do not communicate with each other would only take a
time complexity of O(n) and a space complexity of
O(m), which was what I perceived to be the simplest
solution that was reasonably optimised.2
Finally, once you do find the number of
socially-distancing servers, just subtract from the total
number of servers present to return your answer.
code
class Solution {
public:
int countServers(vector<vector<int>>& grid) {
vector<int> col_counter (grid[0].size(), 0);
unordered_set<int> columns;
int ans = 0, m = grid.size(), n = grid[0].size(), total_count = 0;
for (int i = 0; i < m; ++i) {
int row_counter = 0, temp_index;
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++total_count;
++row_counter;
++col_counter[j];
temp_index = j;
}
}
if (row_counter == 1) columns.insert(temp_index);
}
for (int i : columns) {
if (col_counter[i] == 1) ++ans;
}
return total_count - ans;
}
}