🔥 CỘT MỐC QUAN TRỌNG: Hôm nay đánh dấu NGÀY 30 của Leetcode Daily Challenge, một hành trình đầy cảm xúc! Nếu bạn đã theo dõi từ những ngày đầu tiên, xin chúc mừng 🎉 bạn đã kiên trì và đang dần trở thành một cao thủ thuật toán! 💪

👋 Chào mừng đến với Learning AI With Losers!
Mình là Loser1, và hôm nay chúng ta sẽ cùng nhau giải quyết một bài toán thú vị về hệ thống quản lý số động. Bài toán này yêu cầu chúng ta thiết kế một hệ thống có thể thêm, thay đổi, tìm kiếm các con số một cách hiệu quả.

Input:
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output:
[null, -1, null, null, null, null, 1, null, 2]
Giải thích:
NumberContainers nc = new NumberContainers();
nc.find(10); // Không có chỉ mục nào chứa số 10. Do đó, trả về -1.
nc.change(2, 10); // Container tại chỉ mục 2 sẽ được điền số 10.
nc.change(1, 10); // Container tại chỉ mục 1 sẽ được điền số 10.
nc.change(3, 10); // Container tại chỉ mục 3 sẽ được điền số 10.
nc.change(5, 10); // Container tại chỉ mục 5 sẽ được điền số 10.
nc.find(10); // Số 10 nằm ở các chỉ mục 1, 2, 3 và 5. Vì chỉ mục nhỏ nhất chứa 10 là 1, trả về 1.
nc.change(1, 20); // Container tại chỉ mục 1 sẽ được điền số 20. Lưu ý rằng chỉ mục 1 trước đó chứa 10 và sau đó được thay thế bằng 20.
nc.find(10); // Số 10 nằm ở các chỉ mục 2, 3 và 5. Chỉ mục nhỏ nhất chứa 10 là 2. Do đó, trả về 2.
    

🧠 Intuition

🔍 Đặt vấn đề

Hãy tưởng tượng bạn đang quản lý một kho hàng với hàng triệu hộp (index), và mỗi hộp có thể chứa một con số duy nhất.

Yêu cầu của bài toán:
1️⃣ Thêm hoặc thay đổi số trong một hộp bất kỳ.
2️⃣ Tìm hộp nhỏ nhất chứa số đã cho.

🏪 Tưởng tượng như một hệ thống quản lý kho hàng thông minh:

• Bạn có nhiều hộp, mỗi hộp có một chỉ mục (index).
• Mỗi hộp có thể chứa một số nguyên và bạn có thể cập nhật giá trị bất kỳ lúc nào.
• Nếu ai đó hỏi "Hộp nhỏ nhất chứa số X?", bạn phải trả lời ngay lập tức.

📌 Ví dụ trực quan:

Ban đầu, hệ thống trống rỗng. Bạn bắt đầu thêm các số vào hộp:

[2] → 10   
[1] → 10  
[3] → 10  
[5] → 10  

Nếu có người hỏi:
"Số 10 đang nằm ở hộp nào nhỏ nhất?"
👉 Trả lời: Hộp số 1.

Sau đó, bạn thay đổi hộp 1 → 20, và nếu ai đó lại hỏi:
"Số 10 đang ở hộp nào nhỏ nhất?"
👉 Trả lời: Hộp số 2.

🔍 Nhận xét quan trọng:

• Chúng ta cần một cách nhanh chóng để cập nhật số trong hộp.
• Khi tìm kiếm số, cần trả về hộp có chỉ mục nhỏ nhất ngay lập tức.

🏗 Approach

✅ Ý tưởng chính

Để quản lý hiệu quả việc thay đổi số và truy vấn số nhỏ nhất, ta sử dụng hai cấu trúc dữ liệu chính:

1️⃣ HashMap (index_to_number)

• Ánh xạ một hộp (index) đến con số nó chứa.
• Giúp kiểm tra xem một hộp đang chứa số nào.

2️⃣ Ordered Set (number_freq)

• Lưu danh sách các hộp chứa một số nhất định.
• Dùng set có thứ tự để nhanh chóng tìm hộp nhỏ nhất.

🔥 Cách triển khai từng thao tác

1️⃣ change(index, number):

• Nếu hộp đã chứa số cũ, ta xóa hộp đó khỏi danh sách của số cũ.
• Cập nhật số mới vào hộp.
• Thêm hộp vào danh sách của số mới.

2️⃣ find(number):

• Nếu số không tồn tại, trả về -1.
• Nếu số tồn tại, trả về hộp nhỏ nhất chứa số đó.

📌 Hình minh họa trực quan:

🔹 Trước khi cập nhật:

[1] → 10  
[2] → 10  
[3] → 10  
[5] → 10  

Tìm số 10 👉 Hộp nhỏ nhất là 1

🔹 Sau khi đổi hộp 1 thành 20:

[1] → 20  
[2] → 10  
[3] → 10  
[5] → 10  

Tìm số 10 👉 Hộp nhỏ nhất là 2

🔹 Tất cả thao tác đều nhanh gọn nhờ set và map!

⏳ Complexity Analysis

📌 Tổng độ phức tạp: O(Qlog⁡N)O(Q \log N) với QQ là số truy vấn.

🚀 Giải pháp này cực kỳ tối ưu cho bài toán có số lượng truy vấn lớn!

🚀 Code Implementation

Dưới đây là lời giải C++ sử dụng map và set để đạt hiệu suất tối ưu:

class NumberContainers {
public:
    NumberContainers() {
        // Khởi tạo cấu trúc dữ liệu
    }
    
    void change(int index, int number) {
        // Nếu hộp đã có số cũ, xóa số đó khỏi danh sách
        if (index_to_number.count(index) == 1) {
            int old_number = index_to_number[index];
            number_freq[old_number].erase(index);
            if (number_freq[old_number].empty()) {
                number_freq.erase(old_number);
            }
        }
        // Cập nhật số mới vào hộp
        index_to_number[index] = number;
        number_freq[number].insert(index);
    }
    
    int find(int number) {
        // Trả về hộp nhỏ nhất chứa số nếu tồn tại
        if (number_freq.count(number) == 0) {
            return -1;
        } else {
            return *number_freq[number].begin();
        }
    }

private:
    map<int, int> index_to_number;  // Lưu số hiện tại của mỗi hộp
    map<int, set<int>> number_freq; // Lưu danh sách các hộp chứa số
};

📌 Example Walkthrough

🔹 Input:

["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]

🔹 Output:

[null, -1, null, null, null, null, 1, null, 2]

🔹 Giải thích:
1️⃣ Không tìm thấy số 10, trả về -1.
2️⃣ Thêm số 10 vào hộp 2, 1, 3, 5.
3️⃣ Trả về hộp nhỏ nhất chứa 10 là 1.
4️⃣ Đổi hộp 1 thành 20, hộp nhỏ nhất còn lại chứa 10 là 2.

🌟 Key Takeaways

✅ map giúp lưu trữ dữ liệu linh hoạt.
✅ set giúp tìm kiếm hộp nhỏ nhất hiệu quả.
✅ Giải pháp tối ưu cho dữ liệu lớn.

🔥 Chúc mừng bạn đã hoàn thành thử thách Leetcode Day 30!

📢 Theo dõi Learning AI With Losers để tiếp tục hành trình Leetcode nhé! 🚀

CODE EDITOR

📌 Hashtags:
#leetcode #leetcodedaily #coding #datastructures #algorithms #learningwithlosers