DDSA Solutions

1267. Count Servers that Communicate

MediumView on LeetCode
ArrayCountingMatrix
Time: O(m·n)
Space: O(m+n)

Problem Overview

A server communicates if it shares a row or column with another server.

Intuition

A server communicates if it shares a row or column with another server. Count cells that are 1 and in a row/column with at least one other 1.

Algorithm

  1. 1Count servers per row and per column.
  2. 2For each server: if row_count[r]>1 or col_count[c]>1, it communicates.

Common Pitfalls

  • •Two passes: first count rows/cols, then determine communicating servers.
1267.cs
C#
// Approach: Count servers per row and per column; a server communicates if its row count > 1 or its column count > 1.
// Time: O(m·n) Space: O(m+n)

public class Solution
{
    public int CountServers(int[][] grid)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        int ans = 0;
        int[] rows = new int[m];
        int[] cols = new int[n];

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1)
                {
                    ++rows[i];
                    ++cols[j];
                }
            }
        }

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1))
                    ++ans;
            }
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems