Problem of The Day: Count Servers that Communicate

Problem Statement

Intuition

The problem involves identifying servers that can communicate with at least one other server in the same row or column. My first thought was to simulate the communication network by checking every server and identifying all servers it can directly or indirectly connect to.

Approach

1. Initialization:

   • Create a queue to process each server’s position (row, column) in the grid.
   • Use a seen set to store all unique servers that are part of a communication network.

2. Iterate Through the Grid:

   • Traverse the grid, and for every cell containing 1 (indicating a server), add its position to the queue.

3. Simulate Communication:

   • For each server (r, c) dequeued, traverse the entire row r and column c to find other servers that can communicate with it. Store all these servers’ positions in a visited set.
   • If the size of visited is greater than 1, it means the current server can communicate with others, so update the global seen set with the visited servers.

4. Result:

   • The final size of the seen set gives the count of servers that can communicate with at least one other server.

Complexity

• Time complexity:

  • Traversing the grid takes \(O(R \times C)\), where \(R\) is the number of rows and \(C\) is the number of columns.
  • For each server in the queue, we traverse its entire row and column, which is \(O(R + C)\) for each server. In the worst case, this could add up to \(O(R \times C \times (R + C))\).
  • Therefore, the overall time complexity is \(O(R \times C \times (R + C))\).

• Space complexity:

  • The queue, seen, and visited sets can collectively use up to \(O(R \times C)\) space in the worst case.
  • Hence, the space complexity is \(O(R \times C)\).

Code

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        res = 0
        ROWS = len(grid)
        COLS = len(grid[0])
        queue = deque()
        seen = set()
        for row in range(ROWS):
            for col in range(COLS):
                if grid[row][col] == 1:
                    queue.append([row, col])

        while queue:
            r, c = queue.popleft()
            visited = set()
            for row in range(ROWS):
                if grid[row][c] == 1:
                    visited.add((row, c))
            for col in range(COLS):
                if grid[r][col] == 1:
                    visited.add((r, col))

            if len(visited) > 1:
                seen.update(visited)

        return len(seen)

Editorial

Approach 1: Brute-Force

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        num_rows = len(grid)
        num_cols = len(grid[0]) if num_rows > 0 else 0
        communicable_servers_count = 0

        # Traverse through the grid
        for row in range(num_rows):
            for col in range(num_cols):
                if grid[row][col] == 1:
                    can_communicate = False

                    # Check for communication in the same row
                    for other_col in range(num_cols):
                        if other_col != col and grid[row][other_col] == 1:
                            can_communicate = True
                            break

                    # If a server was found in the same row, increment
                    # communicable_servers_count
                    if can_communicate:
                        communicable_servers_count += 1
                    else:
                        # Check for communication in the same column
                        for other_row in range(num_rows):
                            if other_row != row and grid[other_row][col] == 1:
                                can_communicate = True
                                break

                        # If a server was found in the same column, increment
                        # communicable_servers_count
                        if can_communicate:
                            communicable_servers_count += 1

        return communicable_servers_count

Approach 2: Track Using Two Arrays

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        row_counts = [0] * len(grid[0])
        col_counts = [0] * len(grid)

        # Count servers in each row and each column
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col]:
                    row_counts[col] += 1
                    col_counts[row] += 1

        communicable_servers_count = 0

        # Count servers that can communicate (in the same row or column)
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col]:
                    if row_counts[col] > 1 or col_counts[row] > 1:
                        communicable_servers_count += 1

        return communicable_servers_count

Approach 3: Server Grouping

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        communicable_servers_count = 0
        row_counts = [0] * len(grid[0])
        last_server_in_col = [-1] * len(grid)

        # First pass to count servers in each row and column
        for row in range(len(grid)):
            server_count_in_row = 0
            for col in range(len(grid[0])):
                if grid[row][col]:
                    server_count_in_row += 1
                    row_counts[col] += 1
                    last_server_in_col[row] = col

            # If there is more than one server in the row, increase the count
            if server_count_in_row != 1:
                communicable_servers_count += server_count_in_row
                last_server_in_col[row] = -1

        # Second pass to check if servers can communicate
        for row in range(len(grid)):
            if (
                last_server_in_col[row] != -1
                and row_counts[last_server_in_col[row]] > 1
            ):
                communicable_servers_count += 1
        return communicable_servers_count