We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Servers that Communicate

Difficulty: Medium

Problem 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.

Key Insights

  • Servers can only communicate if they are in the same row or column.
  • We can count the number of servers in each row and each column.
  • A server is counted as communicating if its row or column has more than one server.
  • We can use two arrays to keep track of the number of servers in each row and each column.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m + n)

Solution

To solve the problem, we will use the following approach:

  1. Initialize two arrays to count the servers in each row and each column.
  2. Traverse the grid to fill these arrays with counts of servers.
  3. Traverse the grid again to check each server:
    • If the count of servers in its row or column is greater than one, it can communicate with at least one other server, so we increment the result count.
  4. Return the total count of servers that can communicate.

Code Solutions

def countServers(grid):
    if not grid:
        return 0
    
    m, n = len(grid), len(grid[0])
    row_count = [0] * m
    col_count = [0] * n
    
    # Count the number of servers in each row and column
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                row_count[i] += 1
                col_count[j] += 1
    
    result = 0
    # Count servers that can communicate
    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
← Back to All Questions