1267. Count Servers that Communicate - Explanation

Description

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input: grid = [
    [1,1,0,0],
    [0,0,1,0],
    [0,0,1,0],
    [0,0,0,1]
]

Output: 4

Explanation: Except for the server at the position (3,3), all other servers have other servers to communicate.

Example 2:

Input: grid = [
    [1,0],
    [1,1]
]

Output: 3

Explanation: All three servers can communicate with at least one other server.

Constraints:

1 <= grid.length, grid[i].length <= 250
grid[i][j] == 0 or 1

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

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

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 0:
                    continue

                found = False
                for col in range(n):
                    if col != c and grid[r][col] == 1:
                        found = True
                        break

                if not found:
                    for row in range(m):
                        if row != r and grid[row][c] == 1:
                            found = True
                            break

                if found:
                    res += 1

        return res

Time & Space Complexity

Time complexity: $O(m * n ^ 2)$
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number of columns of the given matrix $grid$ .

2. Iteration

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        row_cnt = [0] * ROWS
        col_cnt = [0] * COLS

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    row_cnt[r] += 1
                    col_cnt[c] += 1

        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] and max(row_cnt[r], col_cnt[c]) > 1:
                    res += 1

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m + n)$

Where $m$ is the number of rows and $n$ is the number of columns of the given matrix $grid$ .

3. Iteration (Space Optimized)

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        res = 0
        ROWS, COLS = len(grid), len(grid[0])

        # Rows
        for r in range(ROWS):
            row_sum = sum(grid[r])
            if row_sum <= 1:
                continue
            res += row_sum
            for c in range(COLS):
                if grid[r][c]:
                    grid[r][c] = -1  # Mark

        # Cols
        for c in range(COLS):
            col_sum = unmarked = 0
            for r in range(ROWS):
                col_sum += abs(grid[r][c])
                if grid[r][c] > 0:
                    unmarked += 1
                elif grid[r][c] < 0:
                    grid[r][c] = 1 # Unmark
            if col_sum >= 2:
                res += unmarked

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number of columns of the given matrix $grid$ .