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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Servers that Communicate

Number: 1396

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg

Problem Description

Given a grid representing a server center (where 1 indicates a server and 0 indicates no server), two servers communicate if they are in the same row or column. Return the number of servers that can communicate with at least one other server.

Key Insights

  • A server can communicate only if there is at least one other server in its row or column.
  • Count the total servers present per row and per column.
  • In a subsequent pass, verify for each server that its corresponding row or column has more than one server.
  • This two-pass method ensures an efficient solution.

Space and Time Complexity

Time Complexity: O(m*n) where m is the number of rows and n is the number of columns. Space Complexity: O(m + n) for storing counts for rows and columns.

Solution

The solution uses a two-pass approach:

  1. First pass: Traverse the grid to count the number of servers in each row and column using simple arrays.
  2. Second pass: For every cell containing a server, check if the corresponding row or column has a count greater than one. If so, count that server as communicating. This approach efficiently leverages the grid structure with a linear scan and minimal extra space.

Code Solutions

# Python code with detailed comments

def countServers(grid):
    m = len(grid)       # Number of rows
    n = len(grid[0])    # Number of columns
    
    # Create lists to count servers in each row and each column
    row_count = [0] * m
    col_count = [0] * n
    
    # First pass: Count servers in every 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
                
    total_servers = 0
    
    # Second pass: Count servers that communicate with at least one other server.
    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):
                total_servers += 1
    return total_servers

# Example usage
grid1 = [[1,0],[0,1]]
print(countServers(grid1))  # Output: 0

grid2 = [[1,0],[1,1]]
print(countServers(grid2))  # Output: 3
← Back to All Questions