Count Servers that Communicate

Medium

Asked by:

57 views

Topics:

Arrays

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,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the grid (number of rows and columns)?
Can the grid contain any values other than 0 or 1?
Is a server considered to be communicating with itself if it's the only server in its row or column?
If there are no communicating servers, what should the return value be?
Do the rows and columns of the grid need to be rectangular (i.e., all rows have the same number of columns)?

Brute Force Solution

Approach

The core idea is to check every server, one at a time. For each server, we will look at all other servers and see if they can communicate with each other.

Here's how the algorithm would work step-by-step:

Pick a server from the grid.
Look at every other server in the grid.
Check if the picked server and the other server are in the same row or in the same column.
If they are in the same row or column, mark that the picked server is able to communicate.
Repeat the process of checking with every other server for all servers in the grid.
Count the number of servers that can communicate with at least one other server.

Code Implementation

def count_servers_that_communicate_brute_force(grid):
    rows = len(grid)
    columns = len(grid[0]) if rows > 0 else 0
    communicating_servers_count = 0

    # Iterate through each server in the grid
    for row_index in range(rows):
        for column_index in range(columns):
            if grid[row_index][column_index] == 1:
                can_communicate = False

                # Check against every other server in the grid
                for other_row_index in range(rows):
                    for other_column_index in range(columns):
                        # Skip checking the server against itself
                        if row_index == other_row_index and column_index == other_column_index:
                            continue

                        # Check if the other server exists
                        if grid[other_row_index][other_column_index] == 1:
                            # Check if they share a row or column
                            if row_index == other_row_index or column_index == other_column_index:
                                # If they share a row or column, communication is possible
                                can_communicate = True
                                break

                    if can_communicate:
                        break

                # Increment count if server can communicate with others
                if can_communicate:
                    communicating_servers_count += 1

    return communicating_servers_count

Big(O) Analysis

Time Complexity

O(n²) – The provided approach iterates through each server in the grid. For each server, it then iterates through all other servers to check for communication in the same row or column. Given that n represents the number of servers in the grid, this involves checking approximately n-1 other servers for each of the n servers. Thus, the number of operations is proportional to n * (n-1), which can be simplified to n * n/2, therefore the time complexity is O(n²).

Space Complexity

O(1) – The provided plain English explanation only describes iterating through the grid and checking for communication based on row and column indices. No auxiliary data structures like lists, hash maps, or sets are created to store information beyond the input grid itself. The algorithm operates in place, using a fixed number of variables for indices and comparison, irrespective of the grid's size (rows x columns). Therefore, the space complexity is constant.

Optimal Solution

Approach

To efficiently find the number of servers that can communicate, the key idea is to focus on the rows and columns where servers are located. We'll count servers by examining rows and columns, not individual servers, to avoid redundant checks. A server can communicate if there's at least one other server in its row or column.

Here's how the algorithm would work step-by-step:

First, count the number of servers in each row and each column.
Then, go through each server in the grid.
For each server, check the row count and column count where it's located.
If either the row count or the column count is greater than one, it means the server can communicate with at least one other server.
Count these communicating servers.

Code Implementation

def count_servers(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0]) if number_of_rows > 0 else 0

    row_counts = [0] * number_of_rows
    column_counts = [0] * number_of_columns

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if grid[row_index][column_index] == 1:
                row_counts[row_index] += 1
                column_counts[column_index] += 1

    communicating_servers_count = 0

    # Iterate through each cell to find communicating servers
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if grid[row_index][column_index] == 1:
                # A server communicates if others share its row or column.
                if row_counts[row_index] > 1 or column_counts[column_index] > 1:

                    communicating_servers_count += 1

    # Return the count of servers that can communicate
    return communicating_servers_count

Big(O) Analysis

Time Complexity

O(m*n) – First, we iterate through the entire grid of size m x n to count the number of servers in each row and column, which takes O(m*n) time. Then, we iterate through the entire grid again to check for each server whether it can communicate with other servers in its row or column, taking another O(m*n) time. Therefore, the total time complexity is O(m*n) + O(m*n), which simplifies to O(m*n), where m is the number of rows and n is the number of columns in the grid.

Space Complexity

O(m + n) – The algorithm uses two auxiliary arrays: one to store the count of servers in each row and another to store the count of servers in each column. If the input grid has m rows and n columns, the row count array will have a size of m, and the column count array will have a size of n. Therefore, the space complexity is proportional to m + n. In the worst-case scenario, where every row and column might have servers, the extra space is O(m + n).

Edge Cases

Case	How to Handle
Null or empty grid input	Return 0 immediately as there are no servers to count.
Grid with only one row or one column	Iterate through the single row or column and count the servers (value of 1) since they inherently communicate within that row/column.
Grid where all servers are isolated (no communication possible)	The algorithm should correctly return 0, as no rows or columns share multiple servers.
Grid where all cells contain servers (all 1s)	The solution should return the total number of cells in the grid since every server communicates with every other server within their row and column.
Grid with very large dimensions (large number of rows and columns)	Ensure the row and column count operations have acceptable time complexity; using O(m*n) space can improve time complexity if acceptable.
Integer overflow potential when summing server counts in large grids	Use a data type capable of holding large counts, such as long in Java/C++ or a similar large integer type.
Input grid contains values other than 0 or 1	Validate the input and either throw an exception or treat any value other than 1 as 0.
A row or column contains only one server	The solution needs to exclude these lone servers when counting communicating servers since they need at least two servers to communicate.

Null or empty grid input

How to Handle:

Return 0 immediately as there are no servers to count.

Grid with only one row or one column

How to Handle:

Iterate through the single row or column and count the servers (value of 1) since they inherently communicate within that row/column.

Grid where all servers are isolated (no communication possible)

How to Handle:

The algorithm should correctly return 0, as no rows or columns share multiple servers.

Grid where all cells contain servers (all 1s)

How to Handle:

The solution should return the total number of cells in the grid since every server communicates with every other server within their row and column.

Grid with very large dimensions (large number of rows and columns)

How to Handle:

Ensure the row and column count operations have acceptable time complexity; using O(m*n) space can improve time complexity if acceptable.

Integer overflow potential when summing server counts in large grids

How to Handle:

Use a data type capable of holding large counts, such as long in Java/C++ or a similar large integer type.

Input grid contains values other than 0 or 1

How to Handle:

Validate the input and either throw an exception or treat any value other than 1 as 0.

A row or column contains only one server

How to Handle:

The solution needs to exclude these lone servers when counting communicating servers since they need at least two servers to communicate.