Medium February 7th, 2025 by Loser1

Table Of Contents

3160. Find the Number of Distinct Colors Among the Balls

Xin chào các chiến hữu của Learning AI With Losers! 👋 Mình là Loser1 đây!

Hôm nay, chúng ta cùng nhau tham gia một bữa tiệc đầy màu sắc với những quả bóng bay rực rỡ. 🚀

Hãy tưởng tượng bạn đang tổ chức một bữa tiệc lớn, nơi mỗi quả bóng cần được sơn màu một cách thông minh. Và thử thách của chúng ta chính là đảm bảo rằng sau mỗi lần sơn, ta có thể nhanh chóng biết được có bao nhiêu màu sắc khác nhau đang xuất hiện.

Sẵn sàng chưa? Cùng nhau bước vào thế giới sắc màu nào! 🎈🎉

3160. Find the Number of Distinct Colors Among the Balls

Medium

Đã giải: 35.7K Công ty: Google

Bạn được cung cấp một số nguyên limit và một mảng 2D queries có kích thước n x 2.
Có limit + 1 quả bóng với nhãn khác nhau trong phạm vi [0, limit]. Ban đầu, tất cả các quả bóng đều chưa được tô màu. Đối với mỗi truy vấn trong queries có dạng [x, y], bạn sẽ tô màu quả bóng x bằng màu y. Sau mỗi truy vấn, bạn cần tìm số lượng màu khác nhau trong các quả bóng.
Trả về một mảng result có độ dài n, trong đó result[i] biểu thị số lượng màu khác nhau sau truy vấn thứ i.

Lưu ý: Việc không có màu sẽ không được tính là một màu.

Example 1:

Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
Output: [1,2,2,3]
Giải thích:
Sau truy vấn 0, quả bóng 1 có màu 4.
Sau truy vấn 1, quả bóng 1 có màu 4, và quả bóng 2 có màu 5.
Sau truy vấn 2, quả bóng 1 có màu 3, và quả bóng 2 có màu 5.
Sau truy vấn 3, quả bóng 1 có màu 3, quả bóng 2 có màu 5, và quả bóng 3 có màu 4.

Example 2:

Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
Output: [1,2,2,3,4]
Giải thích:
Sau truy vấn 0, quả bóng 0 có màu 1.
Sau truy vấn 1, quả bóng 0 có màu 1, và quả bóng 1 có màu 2.
Sau truy vấn 2, quả bóng 0 có màu 1, và các quả bóng 1 và 2 có màu 2.
Sau truy vấn 3, quả bóng 0 có màu 1, các quả bóng 1 và 2 có màu 2, và quả bóng 3 có màu 4.
Sau truy vấn 4, quả bóng 0 có màu 1, các quả bóng 1 và 2 có màu 2, quả bóng 3 có màu 4, và quả bóng 4 có màu 5.

Ràng buộc:

1 <= limit <= 10^9
1 <= n == queries.length <= 10^5
queries[i].length == 2
0 <= queries[i][0] <= limit
1 <= queries[i][1] <= 10^9

📖 Xem Đề bài trên LeetCode 💡 Xem Solution trên LeetCode

🎯 Intuition

Hãy tưởng tượng bạn đang có một túi bóng bay trống trơn. Ban đầu, tất cả đều không có màu sắc gì cả.

🟡 ⚪ ⚪ ⚪ ⚪ ⚪

Mỗi lần bạn lấy một quả bóng ra và tô màu nó. Ví dụ, sau một vài lần sơn, chúng ta có:

🔴 ⚪ 🔵 ⚪ 🟡

Bạn nhận ra rằng mỗi lần tô màu lại, số màu sắc có thể thay đổi.

Nếu bạn sơn một quả bóng bằng một màu mới, số lượng màu sắc khác nhau sẽ tăng lên.
Nếu bạn sơn đè lên một quả bóng đã có màu, màu cũ có thể biến mất, làm giảm tổng số màu sắc hiện có.

Nhiệm vụ của chúng ta là theo dõi những thay đổi này một cách nhanh chóng sau mỗi truy vấn!

💡 Approach

Để giải quyết bài toán này một cách hiệu quả, chúng ta sẽ sử dụng hai bảng băm (hash maps):

✅ Ball Color Map:
Lưu màu sắc hiện tại của từng quả bóng. Ví dụ:

Ball 1 → Color 4
Ball 2 → Color 5

✅ Color Counter:
Theo dõi số lượng quả bóng của từng màu. Ví dụ:

Color 3: 1 ball
Color 4: 2 balls

🎨 Quy trình cập nhật màu

Với mỗi truy vấn [ball, color], chúng ta thực hiện các bước sau:

1️⃣ Xóa màu cũ của bóng (nếu có):

Nếu quả bóng đã có màu trước đó, ta giảm số lượng của màu đó.
Nếu số lượng màu cũ về 0, ta xóa nó khỏi danh sách màu đang có.

2️⃣ Cập nhật màu mới cho bóng:

Thêm màu mới vào bảng băm.
Nếu màu mới xuất hiện lần đầu tiên, số lượng màu sắc độc nhất sẽ tăng lên.

3️⃣ Ghi nhận kết quả:

Sau mỗi truy vấn, lưu lại tổng số màu sắc hiện có.

⏳ Complexity Analysis

Thời gian: Mỗi truy vấn xử lý trong O(1) do chỉ sử dụng bảng băm.
Không gian: Dùng O(n) để lưu thông tin màu sắc của bóng và số lượng màu sắc.

🚀 Code Implementation

C++

class Solution {
public:
    vector<int> queryResults(int limit, vector<vector<int>>& queries) {
        unordered_map<int, int> ballColor;    // Lưu màu hiện tại của từng bóng
        unordered_map<int, int> colorCount;   // Đếm số lượng mỗi màu
        vector<int> result;
        int distinctColors = 0;
        
        for (auto& query : queries) {
            int ball = query[0], color = query[1];
            
            // Xử lý màu cũ nếu bóng đã được tô trước đó
            if (ballColor.count(ball)) {
                int oldColor = ballColor[ball];
                if (--colorCount[oldColor] == 0) {
                    colorCount.erase(oldColor);
                    distinctColors--;
                }
            }
            
            // Cập nhật màu mới
            ballColor[ball] = color;
            if (++colorCount[color] == 1) {
                distinctColors++;
            }
            
            result.push_back(distinctColors);
        }
        
        return result;
    }
};

🎯 Example Walkthrough

Hãy cùng xem một ví dụ cụ thể!

Input:

C++

limit = 4;
queries = [[1,4], [2,5], [1,3], [3,4]];

💡 Bước 1: [1,4]

Bóng 1 được tô màu 4.
Màu sắc độc nhất: {4} → Kết quả: [1]

💡 Bước 2: [2,5]

Bóng 2 được tô màu 5.
Màu sắc độc nhất: {4, 5} → Kết quả: [1, 2]

💡 Bước 3: [1,3]

Bóng 1 đổi từ màu 4 sang 3.
Cập nhật: Xóa màu 4 (vì không còn bóng nào có màu này).
Màu sắc độc nhất: {3, 5} → Kết quả: [1, 2, 2]

💡 Bước 4: [3,4]

Bóng 3 được tô màu 4.
Màu sắc độc nhất: {3, 5, 4} → Kết quả: [1, 2, 2, 3]

✨ Final Output: [1, 2, 2, 3]

🔥 Key Takeaways

✅ Hiệu quả với hash map – Cho phép cập nhật nhanh màu sắc từng bóng.
✅ Cập nhật động – Theo dõi số lượng từng màu một cách linh hoạt.
✅ Xử lý trong O(1) – Mỗi truy vấn được thực hiện trong thời gian hằng số.

🎉 Conclusion

Đây là một bài toán cực kỳ thú vị khi phải quản lý dữ liệu động một cách hiệu quả! Bài toán này không chỉ rèn luyện kỹ năng sử dụng hash map, mà còn giúp chúng ta hiểu rõ cách theo dõi sự thay đổi của dữ liệu qua các truy vấn liên tiếp.

Cảm ơn bạn đã đồng hành cùng Learning AI With Losers trong thử thách Leetcode Daily Challenge hôm nay! 🚀

📌 Đừng quên theo dõi để không bỏ lỡ những bài toán thú vị tiếp theo nhé!

👉 Follow Fanpage: Learning AI With Losers
👉 Website chính thức: learningaiwithlosers.com