1267: Count-Servers-that-Communicate
Medium
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;
}
}