Count Servers that Communicate - Leetcode 1267 - Python

0:00 - Read the problem
3:30 - Drawing Explanation
5:58 - Coding Explanation
8:14 - Space Optimization

leetcode 1267

#neetcode #leetcode #python

[yhbarve]

I was able to solve this one on my own. Let's go!

[md_pedia]

Instead of checking for connected servers we could kinda check for isolated servers and simply deduct their cnt from the total cnt

[shahukor]

More optimal approach :
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
res = 0
for r in range(len(grid)):
sumofrow = sum(grid[r])
if sumofrow>1:
res+=sumofrow

elif sumofrow==1:
columnnumber = grid[r].index(1)
if sum(grid[r][columnnumber] for r in range(len(grid)))>1:
res+=1
return res

1. Check the sum of each row.
2. If the sum > 1, add it to the result (servers connected row-wise).
3. If the sum == 1, check the column sum for that server. (sum==1 means there is only 1 server in that row but there is a possibility that it might be connected column-wise with other servers)
4. If the column sum > 1, add that server to the result (res+=1), since it is connected column-wise to other servers.

[myyfstz]

sheesh i breezed past this one holy moly in a matter of seconds, so not watching this vid haha. Leetcode + Neetcode is the name of the game 🍆🍆🍆 we are only starting. Keep going, boss!

[kyledang]

i watch your videos so much that the solution i came up with matches yours exactly

[JamesBond-mqpd]

For me, this is a difficult problem. I tried to solve it using dynamic programming but couldn't break the task down into subproblems. I would never have come up with the idea that if the number of columns or rows is greater than 1, you just need to increment. The author of the video is a genius.

[saidud]

Big fan of your explanation! Binary search is very hard for me even though I've solved many LC problems, BS still eats my brain to write an AC. Could you please do a summary video on binary search on when to go with l<=r, l<r, ... when to return left, return right, return mid 😃

[kalrajasleen]

3:32 can you please explain how m+n time complexity

[danijelbosnar]

So code on 8:05 should be correct? I do not really think so, since it returns 4 for grid [[1, 0, 1, 0], [0, 1, 0, 1]] where it should be 0, or I got something wrong? To assume that if you have more than one server in a row or column that it means that they are communicating i.e. they must be neighbours?

[PedanticAnswerSeeker]

class Solution:
def countServers(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])

# Step 1: Count servers in each row and column
row_count = [0] * m
col_count = [0] * n

for i in range(m):
for j in range(n):
if grid[i][j] == 1:
row_count[i] += 1
col_count[j] += 1

# Step 2: For each cell with a server, check if it communicates
# (i.e., if row_count or col_count > 1)
result = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and (row_count[i] > 1 or col_count[j] > 1):
result += 1

return result

[igorgomes]

You can improve the performance by counting the total amount of servers in the first traversal and then decrement then isolated server, as follows:
1. Instead of storing in the ROWS array only the count, you will store a tuple with (count, column of last server counted). For rows with a single server, we'll know in which column it is.
2. Also, in this same traversal, keep track of the total count of servers.
3. After this, we don't need to traverse the entire matrix again.
4. For each row in ROWS, if row[0] (count) is equal to 1, check if COLS[row[1] (column of the single server in the row)] is also equal to 1. Is so, decrement total by 1.
5. Return total.

[rajGg-hg]

class Solution:
def countServers(self, grid):
ans = 0
rows = len(grid)
cols = len(grid[0])

for i in range(rows):
cnt = 0
for j in range(cols):
if grid[i][j] == 1:
cnt += 1
if cnt > 1:
ans += cnt
for j in range(cols):
if grid[i][j] == 1:
grid[i][j] = -1

for i in range(cols):
cnt = 0
fcnt = 0
for j in range(rows):
if grid[j][i] == -1:
fcnt += 1
if grid[j][i] == 1:
cnt += 1
if cnt + fcnt > 1:
ans += cnt

return ans

What do you think ?

[LasTCursE]

I've solved it already, but I'm wondering if it's possible instead of incrementing 1 by 1, if we find a server that has connections on either a row or column, can't we just increment the servers by the sum of all servers in the row/column and shrink the matrix?

[jeehar]

My sol:
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
res = 0
for i in range(m):
row_count = 0
k = None
for j in range(n):
if grid[i][j]:
if row_count == 0:
k = j
row_count += 1

res += row_count if row_count != 1 or any(grid[x][k] for x in range(m) if x != i) else 0

return res

[EranM]

did it without additional data structure.

[RubenGarciaCS]

fuck. I was trying to increment the answer while computing the 2 arrays at first.