1267. Count Servers that Communicate

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/count-servers-that-communicate
• topics: 2D Array, Hash Table

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.

Idea

Assign a unique ID to each server and add it to the corresponding row and column dictionaries. Then, count the number of unique IDs for rows and columns that have multiple servers.

Code

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        num_rows, num_cols = len(grid), len(grid[0])
        
        # Dictionaries to track server IDs in each row and column
        row_servers = defaultdict(list)
        col_servers = defaultdict(list)
        
        # Assign a unique ID to each server
        server_id = 0
        for row in range(num_rows):
            for col in range(num_cols):
                if grid[row][col] == 1:  # If there's a server
                    row_servers[row].append(server_id)
                    col_servers[col].append(server_id)
                    server_id += 1
        
        # Set to track servers that are connected
        connected_servers = set()
        
        # Check rows and columns for connected servers
        for server_group in [row_servers, col_servers]:
            for key, server_ids in server_group.items():
                if len(server_ids) > 1:  # Multiple servers in the same row/column
                    connected_servers.update(server_ids)
        
        # Return the count of connected servers
        return len(connected_servers)