Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

Daily LeetCode Challenge Day 14: 1267. Count Servers that Communicate – Network Magic! 🌐

Xin chào mọi người! Mình là Loser1 từ Learning AI with Loser. Hôm nay chúng ta sẽ giải quyết một bài toán thú vị về mạng lưới server! Let’s connect! 🚀

Chào anh em, các ae có thể xem Đề bàiSolution của mình trên LeetCode nhé:

1267. Count Servers that Communicate

Medium
Đã giải

Bạn được cung cấp một bản đồ trung tâm máy chủ, được biểu diễn dưới dạng ma trận số nguyên grid kích thước m x n, trong đó:

  • 1: Có máy chủ tại ô này.
  • 0: Không có máy chủ tại ô này.

Hai máy chủ được coi là có thể giao tiếp nếu chúng nằm trên cùng một hàng hoặc cùng một cột.

Trả về số lượng máy chủ có thể giao tiếp với ít nhất một máy chủ khác.

Ví dụ 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Giải thích: Không có máy chủ nào có thể giao tiếp với máy chủ khác.
Example 1

Ví dụ 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Giải thích: Cả ba máy chủ đều có thể giao tiếp với ít nhất một máy chủ khác.
Example 2

Ví dụ 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Giải thích: Hai máy chủ ở hàng đầu tiên có thể giao tiếp với nhau. Hai máy chủ trong cột thứ ba cũng có thể giao tiếp với nhau. Máy chủ ở góc dưới bên phải không thể giao tiếp với bất kỳ máy chủ nào khác.
Example 3

Ràng buộc:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 250
  • grid[i][j]0 hoặc 1.

Problem Statement

Cho một ma trận grid m*n, trong đó:

  • grid[i][j] = 1: có server
  • grid[i][j] = 0: không có server

Hai server được coi là communicate với nhau nếu chúng nằm cùng hàng hoặc cùng cột.
Nhiệm vụ: Tìm số lượng server có thể communicate với ít nhất một server khác.

First Thoughts & Intuition

Xin chào, Loser1 đây! Khi nhìn vào bài này, mình liên tưởng đến một trung tâm dữ liệu khổng lồ với các máy chủ được kết nối theo grid! 🏢

1. Phân tích Trực quan 🎯

Hãy xem xét một ví dụ đơn giản:

Trung tâm dữ liệu của chúng ta:
1  1  0  0    Server 1 ←→ Server 2  (kết nối theo hàng)
0  0  1  0
0  0  1  0         Server 3         (kết nối theo cột)
0  0  0  1         Server 4         (đơn độc)

2. Mental Model 🧠

Tưởng tượng mỗi server như một node trong mạng:

Các kết nối theo hàng:      Các kết nối theo cột:
🔵──🔵  ⭕️  ⭕️            🔵  🔵  ⭕️  ⭕️
⭕️  ⭕️  🔵  ⭕️     +      ⭕️  ⭕️  🔵  ⭕️
⭕️  ⭕️  🔵  ⭕️            ⭕️  ⭕️  🔵  ⭕️
⭕️  ⭕️  ⭕️  🔵            ⭕️  ⭕️  ⭕️  🔵

= Tổng hợp kết nối cuối cùng:
🟦──🟦  ⬜️  ⬜️
⬜️  ⬜️  🟨  ⬜️
⬜️  ⬜️  🟨  ⬜️
⬜️  ⬜️  ⬜️  ⭕️

3. Breaking Down The Problem 🔍

  1. Định nghĩa "communicate":
   Server A ↔ Server B nếu:
   - Cùng hàng: grid[i][j1] = grid[i][j2] = 1
   - HOẶC cùng cột: grid[i1][j] = grid[i2][j] = 1
  1. Các trường hợp quan trọng:
   Case 1: Đơn độc        Case 2: Kết nối hàng    Case 3: Kết nối cột
   0  0  0                1  1  0                  1  0  0
   0  1  0                0  0  0                  1  0  0
   0  0  0                0  0  0                  0  0  0
   Count: 0               Count: 2                 Count: 2

4. Key Observations 🔑

  1. Optimization Insight:
   Thay vì check từng cặp:      Dùng frequency counting:
   O(n^2) operations            rows = {0: 2, 2: 1}
   ↓                            cols = {0: 1, 2: 2}
   Server 1 → check all         ↓
   Server 2 → check all         Server at (i,j) communicates
   ...                          if rows[i] > 1 || cols[j] > 1
  1. Pattern Recognition:
   Standalone Pattern:    Connected Pattern:
   1  0  0               1  1  0
   0  0  0       vs      1  0  0
   0  0  1               0  0  0
   (0 communicate)       (3 communicate)

5. Visualization của Solution 🎨

Step 1: Count           Step 2: Check          Step 3: Result
1  1  0                rows[0] = 2            🟦🟦⬜️
1  0  0    →          cols[0] = 2    →       🟦⬜️⬜️
0  0  1                rows[2] = 1            ⬜️⬜️⭕️

{r0:2, r2:1}          Server(0,0): ✅        Communicate: 3
{c0:2, c2:1}          Server(0,1): ✅        Non-comm: 1
                      Server(1,0): ✅
                      Server(2,2): ❌

Đây là cách tư duy "frequency-based" thay vì "pair-checking", giúp tối ưu hóa solution của chúng ta! 🚀

Note: Các ký hiệu:

  • 🟦: Server communicate qua hàng
  • 🟨: Server communicate qua cột
  • ⭕️: Server không communicate
  • ⬜️: Không có server

Approach

  1. Đếm frequency:
  • Dùng 2 hashmap đếm số server trên mỗi hàng/cột
  • Key: index hàng/cột
  • Value: số lượng server
  1. Check communicate:
  • Với mỗi server:
    • Communicate nếu row[i] > 1 (có server khác cùng hàng)
    • HOẶC col[j] > 1 (có server khác cùng cột)
  1. Kết quả:
  • Tổng số server thỏa điều kiện

Code Implementation

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        unordered_map<int, int> rows, cols;

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

        // Count communicating servers
        int result = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    if(rows[i] > 1 || cols[j] > 1) {
                        result++;
                    }
                }
            }
        }

        return result;
    }
};

Example Walkthrough

Cùng phân tích ví dụ:

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

Step 1: Count frequencies
- Duyệt ma trận:
  * (0,0)=1 → rows[0]=1, cols[0]=1
  * (1,0)=1 → rows[1]=1, cols[0]=2
  * (1,1)=1 → rows[1]=2, cols[1]=1
  * (2,2)=1 → rows[2]=1, cols[2]=1

Step 2: Check each server
(0,0): cols[0]=2 → communicate!
(1,0): cols[0]=2 AND rows[1]=2 → communicate!
(1,1): rows[1]=2 → communicate!
(2,2): rows[2]=1 AND cols[2]=1 → không communicate ❌

Result: 3 servers communicate!

Visualization:

1  0  0     🟦⬜️⬜️
1  1  0  →  🟦🟨⬜️
0  0  1     ⬜️⬜️⭕️

🟦🟨: Communicate servers
⭕️: Non-communicate server

Complexity Analysis

  • Time: O(m * n) - duyệt ma trận 2 lần
  • Space: O(m + n) - lưu hashmap rows và cols

Tips & Tricks

  1. HashMap giúp đếm frequency hiệu quả
  2. Check communicate chỉ cần OR (không cần AND)
  3. Tránh check từng cặp server → dùng frequency

Chúc mọi người code vui! Hẹn gặp lại trong các bài Leetcode tiếp theo! 🚀

P/S: Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨

CODE EDITOR

#leetcode #leetcodedaily #algorithms #programming #learningwithlosers

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Transport quote request logi transports fast & reliable heavy equipment transport & transport services.