1267. Count Servers that Communicate


Problem Description

In this problem, we're given a representation of a server center as a m * n integer matrix called grid, where each cell in the grid can either contain a server (represented by the number 1) or not contain a server (represented by the number 0). The crucial point to understand is that servers are considered to be able to communicate with each other if and only if they are located in the same row or the same column. The objective is to calculate how many servers are able to communicate with at least one other server within the grid.

Intuition

To determine the number of servers that can communicate with others, we need a way to check each server and see if there is at least one other server on the same row or column. The solution approach can start by keeping two separate arrays, row and col, to keep track of how many servers are on each row and column respectively.

We then iterate over the entire grid, counting how many servers are in each row and in each column. This is done by going through each cell of the matrix, and whenever we encounter a server (a cell with a value of 1), we increment the corresponding row and column counters by 1.

Once we have the counts of servers in each row and column, we can again iterate over the grid. This time, for each server, we check whether the corresponding row or column has more than one server (which means the count is greater than 1). If so, the server can communicate with others, and it should be included in the final count. We do this check using a generator expression and pass it to sum function to get the total count of servers that can communicate.

This approach efficiently factors in both row-wise and column-wise communication, ensuring no double counting of servers.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The implementation of the solution uses a two-pass algorithm across the rows and columns of the server grid matrix. The algorithm selectively counts and then aggregates server connections based on the communication criteria. The solution leverages simple data structures – two lists named row and col – to store the counts of servers in each row and column, respectively.

Here's a step-by-step walk-through of the algorithm:

  1. Initialize two lists, row and col, with a size equal to the number of rows m and columns n in input grid, respectively, and set all values to 0. These lists hold counts of servers in each row and column.

    1row = [0] * m
    2col = [0] * n
  2. Iterate over each cell in the grid matrix to fill in the row and col arrays. Whenever a server (1 in grid) is found, increment the respective row's and column's count.

    1for i in range(m):
    2    for j in range(n):
    3        if grid[i][j]:
    4            row[i] += 1
    5            col[j] += 1
  3. After populating the row and col arrays, we carry out a second iteration over the grid. For each server found, check if it can communicate (i.e., if row[i] or col[j] is greater than 1).

    The expression grid[i][j] and (row[i] > 1 or col[j] > 1) evaluates to True if there is a server in grid[i][j] and it can communicate with at least one server in the same row or column.

    The generator expression inside the sum function goes through all cells in the grid, evaluates the above condition, and if it is True, it contributes 1 toward the sum, effectively counting the server.

    1return sum(
    2    grid[i][j] and (row[i] > 1 or col[j] > 1)
    3    for i in range(m)
    4    for j in range(n)
    5)

This code bypasses a separate conditional branching for each server and instead uses a compact generator expression to do the counting, which is a common Pythonic pattern for concise and readable code. The main algorithmic insight is that by keeping track of the row and column server counts, we can determine the capability of each server to communicate in constant time during the second iteration.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we have a server grid grid represented by the following 3 x 4 matrix:

1[
2  [1, 0, 0, 1],
3  [0, 1, 1, 0],
4  [0, 0, 1, 0]
5]

Let's walk through the solution step-by-step for this example:

  1. Initialize two lists, row and col, each with values initialized at 0. For our grid, row will have 3 elements and col will have 4 elements, corresponding to the number of rows and columns in grid, respectively.

    After initialization:

    1row = [0, 0, 0]
    2col = [0, 0, 0, 0]
  2. We iterate over each cell in the grid to count the number of servers in each row and column.

    After completing this step for our example, the row and col lists will look like this:

    1row = [2, 2, 1]
    2col = [1, 1, 2, 1]

    The row list tells us that the first and second rows each have 2 servers, while the third row has 1 server. The col list tells us that the first, second, and fourth columns each have 1 server, and the third column has 2 servers.

  3. Next, we perform a second iteration over the grid. This time, for each server, we check if it can communicate with others. If row[i] or col[j] is greater than 1, the server can communicate.

    • For grid[0][0], we have a server and row[0] > 1 (because row[0] is 2) - so this server can communicate.
    • For grid[0][3], we have a server, but neither row[0] > 1 nor col[3] > 1 (because row[0] is 2, but col[3] is 1) - so this server cannot communicate.
    • For grid[1][1], we have a server and both row[1] > 1 and col[1] > 1, which means this server can communicate.
    • For grid[1][2], we have a server and col[2] > 1, so this server can communicate.
    • For grid[2][2], we do have a server but since row[2] is not greater than 1, this server cannot communicate.

    We continue performing this check for every cell in the grid that contains a server (1).

    Using the generator expression provided, we count the servers that can communicate, which evaluates to 3 for our example (grid[0][0], grid[1][1], and grid[1][2]).

Therefore, for the grid given in our example, the total number of servers that can communicate with at least one other server is 3.

Solution Implementation

1class Solution:
2    def count_servers(self, grid: List[List[int]]) -> int:
3        # Number of rows and columns in the grid
4        num_rows, num_cols = len(grid), len(grid[0])
5      
6        # Arrays to keep track of the count of servers in each row and column
7        rows = [0] * num_rows
8        columns = [0] * num_cols
9      
10        # First pass: count the number of servers in each row and column
11        for i in range(num_rows):
12            for j in range(num_cols):
13                if grid[i][j] == 1:
14                    rows[i] += 1
15                    columns[j] += 1
16      
17        # Second pass: count the number of servers that can communicate
18        # Servers can communicate if they are in the same row or column with another server
19        server_count = 0
20        for i in range(num_rows):
21            for j in range(num_cols):
22                # Check if there's a server and if it's not the only server in its row or column
23                if grid[i][j] == 1 and (rows[i] > 1 or columns[j] > 1):
24                    server_count += 1
25      
26        return server_count
27
1class Solution {
2    public int countServers(int[][] grid) {
3        int numRows = grid.length; // Number of rows in the grid
4        int numCols = grid[0].length; // Number of columns in the grid
5      
6        // Arrays to store the count of servers in each row and column
7        int[] rowCount = new int[numRows];
8        int[] colCount = new int[numCols];
9      
10        // First iteration to fill in the rowCount and colCount arrays
11        for (int i = 0; i < numRows; ++i) {
12            for (int j = 0; j < numCols; ++j) {
13                // Count servers in each row and column
14                if (grid[i][j] == 1) {
15                    rowCount[i]++;
16                    colCount[j]++;
17                }
18            }
19        }
20      
21        // Counter for the total number of connected servers
22        int connectedServers = 0;
23      
24        // Second iteration to count the servers that can communicate
25        // Servers can communicate if they are not the only one in their row or column
26        for (int i = 0; i < numRows; ++i) {
27            for (int j = 0; j < numCols; ++j) {
28                if (grid[i][j] == 1 && (rowCount[i] > 1 || colCount[j] > 1)) {
29                    connectedServers++;
30                }
31            }
32        }
33      
34        // Return the number of connected servers
35        return connectedServers;
36    }
37}
38
1#include <vector>
2
3class Solution {
4public:
5    int countServers(std::vector<std::vector<int>>& grid) {
6        int rowCount = grid.size();            // number of rows in the grid
7        int colCount = grid[0].size();         // number of columns in the grid
8      
9        // Create a vector to store the count of servers in each row and column
10        std::vector<int> serversInRow(rowCount, 0);
11        std::vector<int> serversInColumn(colCount, 0);
12
13        // Calculate the number of servers in each row and column
14        for (int i = 0; i < rowCount; ++i) {
15            for (int j = 0; j < colCount; ++j) {
16                if (grid[i][j]) {  // if there is a server at position (i, j)
17                    ++serversInRow[i];      // increment the count for the row
18                    ++serversInColumn[j];   // increment the count for the column
19                }
20            }
21        }
22      
23        // Count the number of servers that can communicate with at least one other server
24        int serverCount = 0;  // variable to keep track of the total count
25        for (int i = 0; i < rowCount; ++i) {
26            for (int j = 0; j < colCount; ++j) {
27                // A server at (i, j) can communicate if there are other servers in the same
28                // row or column (hence, count will be more than 1 for that row or column).
29                if (grid[i][j] && (serversInRow[i] > 1 || serversInColumn[j] > 1)) {
30                    serverCount++;
31                }
32            }
33        }
34      
35        return serverCount;  // Return the total count of servers that can communicate
36    }
37};
38
1function countServers(grid: number[][]): number {
2    // Get the number of rows (m) and columns (n) from the grid.
3    const rowCount = grid.length;
4    const colCount = grid[0].length;
5
6    // Initialize arrays to keep track of server counts in each row and column.
7    const rowServerCounts = new Array(rowCount).fill(0);
8    const colServerCounts = new Array(colCount).fill(0);
9
10    // First pass: Count the number of servers in each row and column.
11    for (let rowIndex = 0; rowIndex < rowCount; rowIndex++) {
12        for (let colIndex = 0; colIndex < colCount; colIndex++) {
13            if (grid[rowIndex][colIndex] === 1) {
14                rowServerCounts[rowIndex]++;
15                colServerCounts[colIndex]++;
16            }
17        }
18    }
19
20    // Initialize a variable to keep track of the total number of connected servers.
21    let connectedServers = 0;
22
23    // Second pass: Determine if each server is connected horizontally or vertically.
24    for (let rowIndex = 0; rowIndex < rowCount; rowIndex++) {
25        for (let colIndex = 0; colIndex < colCount; colIndex++) {
26            // If there's a server and there's more than one server in the current row or column,
27            // it is considered connected.
28            if (grid[rowIndex][colIndex] === 1 && (rowServerCounts[rowIndex] > 1 || colServerCounts[colIndex] > 1)) {
29                connectedServers++;
30            }
31        }
32    }
33
34    // Return the total count of connected servers.
35    return connectedServers;
36}
37

Time and Space Complexity

Time Complexity

The given code consists of two main parts: The first part is a double loop that goes through the entire grid to count the number of servers in each row and column. Since this loop goes through all the elements of the m x n grid exactly once, the time complexity for this part is O(m * n).

The second part of the code calculates the sum with a generator expression that also iterates through every element in the grid. It checks if there's a server in the given cell (grid[i][j]) and if there is more than one server in the corresponding row or column. Since this is done for each element, it also has a time complexity of O(m * n).

Therefore, the total time complexity of the entire function is O(m * n) + O(m * n), which simplifies to O(m * n) because we only take the highest order term for big O notation.

Space Complexity

For space complexity, the code uses additional arrays row and col to store the counts of servers in each row and column, respectively. The size of row is m and the size of col is n. Hence, the extra space used is O(m + n).

In conclusion, the time complexity is O(m * n) and the space complexity is O(m + n).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄