Count Servers that Communicate - Practice Coding Problems

Count Servers that Communicate - Problem

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

Input & Output

Example 1 — Basic Case

$ Input: grid = [[1,0],[0,1]]

› Output: 0

💡 Note: No server can communicate with any other server. Server at (0,0) has no other server in row 0 or column 0. Server at (1,1) has no other server in row 1 or column 1.

Example 2 — Same Row Communication

$ Input: grid = [[1,0],[1,1]]

› Output: 3

💡 Note: Server (1,0) and (1,1) can communicate (same row). Server (0,0) and (1,0) can communicate (same column). All 3 servers can communicate.

Example 3 — Mixed Communication

$ Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]

› Output: 4

💡 Note: Servers (0,0) and (0,1) communicate via same row. Servers (1,2) and (2,2) communicate via same column. Server (3,3) is isolated. Total: 4 servers communicate.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Matrix with 1s representing servers, 0s representing empty cells

Communication Rules

Servers communicate if they share the same row or column

Count Result

Number of servers that can communicate with at least one other server

Key Takeaway

🎯 Key Insight: A server communicates if its row or column contains more than one server

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is that a server can communicate if and only if there's at least one other server in its row or column. Best approach uses two-pass counting: first pass counts servers per row/column, second pass identifies communicating servers. Time: O(mn), Space: O(m + n)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Count	O(mn)	O(m + n)	First pass counts servers per row/column, second pass identifies communicating servers
Brute Force	O(m²n²)	O(1)	For each server, check all other servers to see if any share the same row or column

Two-Pass Count — Algorithm Steps

Count servers in each row and column
Scan grid again
For each server, check if its row or column count > 1

Visualization

Tap to expand

Step-by-Step Walkthrough

First Pass

Count servers in each row and column

Second Pass

Check each server's row/column count

Result

Count servers with count > 1 in their row or column

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** grid, int gridSize, int* gridColSize) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int m = gridSize, n = gridColSize[0];
    
    // Count servers in each row and column
    int* rowCount = (int*)calloc(m, sizeof(int));
    int* colCount = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                rowCount[i]++;
                colCount[j]++;
            }
        }
    }
    
    // Count communicating servers
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                if (rowCount[i] > 1 || colCount[j] > 1) {
                    count++;
                }
            }
        }
    }
    
    free(rowCount);
    free(colCount);
    return count;
}

int main() {
    // Simple parsing for small test cases
    int grid[3][3] = {{1,0,1},{0,1,0},{1,0,1}};
    int* gridPtrs[3] = {grid[0], grid[1], grid[2]};
    int gridColSize[3] = {3, 3, 3};
    
    int result = solution(gridPtrs, 3, gridColSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Two passes through the grid: first to count, second to check

✓ Linear Growth

Space Complexity

O(m + n)

Arrays to store row and column counts

⚡ Linearithmic Space

32.1K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler