🧩 2364. Count Number of Bad Pairs

👋 Chào mừng mọi người quay trở lại với Learning AI with Losers! Hôm nay, chúng ta sẽ tiếp tục Day 31 của series Leetcode Daily Challenge với một bài toán thú vị: “Đếm số lượng cặp tệ (bad pairs)”.

Trước khi bắt tay vào giải quyết bài toán, hãy cùng tưởng tượng một chút nhé!

🖼 Minh họa trực quan:
Hãy tưởng tượng bạn đang xếp những viên bi theo hàng ngang. Nếu một viên bi đáng lẽ phải nằm ở vị trí phù hợp nhưng lại lệch đi so với quy luật, chúng ta sẽ gọi đó là một bad pair.

Input: nums = [4,1,3,3]
Output: 5
Giải thích:
Cặp (0, 1) là bad pair vì 1 - 0 != 1 - 4.
Cặp (0, 2) là bad pair vì 2 - 0 != 3 - 4, 2 != -1.
Cặp (0, 3) là bad pair vì 3 - 0 != 3 - 4, 3 != -1.
Cặp (1, 2) là bad pair vì 2 - 1 != 3 - 1, 1 != 2.
Cặp (2, 3) là bad pair vì 3 - 2 != 3 - 3, 1 != 0.
Tổng cộng có 5 bad pairs, vì vậy trả về 5.
    

Input: nums = [1,2,3,4,5]
Output: 0
Giải thích:
Không có bad pairs nào.
    

🎯 Problem Breakdown

📜 Đề bài

Bạn được cho một mảng số nguyên nums được đánh chỉ số từ 0. Một cặp chỉ số (i, j) được gọi là cặp xấu (bad pair) nếu thỏa mãn:

• i < j: chỉ số i phải nhỏ hơn chỉ số j
• j - i ≠ nums[j] - nums[i]: khoảng cách giữa hai chỉ số không bằng khoảng cách giữa hai giá trị tương ứng

Nói cách khác, một cặp được coi là "xấu" khi độ chênh lệch giữa các vị trí (j - i) không bằng độ chênh lệch giữa các giá trị tại những vị trí đó (nums[j] - nums[i]).

Ví dụ cho dễ hiểu:

nums = [4,1,3,3] Xét cặp (0,1): - j - i = 1 - 0 = 1 - nums[j] - nums[i] = nums[1] - nums[0] = 1 - 4 = -3 Do 1 ≠ -3 nên (0,1) là một cặp xấu

Hay nói cách khác, nếu sự chênh lệch về chỉ số không khớp với sự chênh lệch về giá trị thì cặp đó là một bad pair.

🔍 Ví dụ minh họa

Example 1

🔹 Input: nums = [4,1,3,3]
🔹 Output: 5
🔹 Giải thích:

Tổng cộng có 5 bad pairs.

Example 2

🔹 Input: nums = [1,2,3,4,5]
🔹 Output: 0
🔹 Giải thích: Không có bad pairs vì mọi phần tử đều tuân theo quy luật.

💡 Intuition

Bài toán yêu cầu đếm số lượng bad pairs, nhưng kiểm tra từng cặp (i, j) bằng cách duyệt brute-force sẽ tốn O(n²), quá chậm với n ≤ 10⁵.

Ta có thể biến đổi điều kiện:
j - i ≠ nums[j] - nums[i]

Suy ra:
nums[j] - j ≠ nums[i] - i

Hay nói cách khác, ta sẽ kiểm tra sự khác biệt giữa giá trị và chỉ số.

Nếu có nhiều phần tử có cùng giá trị nums[i] - i, thì chúng sẽ tạo thành good pairs.

Cuối cùng, số lượng bad pairs sẽ là:

total pairs - good pairs

🔑 Approach

• Tính tổng số cặp có thể có:
  total pairs = n * (n - 1) / 2
  Đây là công thức tính số cặp (i, j) với i < j.
• Duyệt qua mảng, lưu tần suất của từng giá trị nums[i] - i vào một hash map.
• Nếu một giá trị xuất hiện nhiều lần, số lượng good pairs là số cách chọn 2 phần tử từ nhóm này.
• Suy ra số lượng bad pairs bằng cách trừ đi số lượng good pairs khỏi tổng số cặp.

📌 Ví dụ với nums = [4,1,3,3]

• Tổng số cặp: (4 * (4 - 1)) / 2 = 6
• Số good pairs từ giá trị 0: C(2,2) = 1
• Suy ra số bad pairs: 6 - 1 = 5 ✅

⏳ Complexity Analysis

• Time Complexity: O(n), vì chỉ duyệt mảng một lần và sử dụng hash map.
• Space Complexity: O(n), vì cần lưu hash map.

💻 Code Implementation

class Solution {
public:
    long long combinations(int n) {
        return 1LL * n * (n - 1) / 2;  
    }

    long long countBadPairs(vector<int>& nums) {
        map<int, int> number_to_freq;
        long long cnt_good_pairs = 0; 

        for (int i = 0; i < nums.size(); i++) {
            number_to_freq[nums[i] - i] += 1;
        }

        for (auto it : number_to_freq) {
            if (it.second > 1) { 
                cnt_good_pairs += combinations(it.second);
            }
        }

        return combinations(nums.size()) - cnt_good_pairs;
    }
};

🎨 Visualization

Hãy tưởng tượng các phần tử trong nums như các điểm trên một đồ thị.

📌 Nếu ta vẽ các điểm (i, nums[i]), thì các điểm có cùng giá trị nums[i] - i sẽ nằm trên cùng một đường thẳng!

Ví dụ, với nums = [4,1,3,3]:

• Giá trị nums[i] - i = 0 xuất hiện 2 lần, tạo ra 1 good pair.
• Các cặp còn lại là bad pairs!

🖼 Hình minh họa:

Index:  0   1   2   3  
Nums:   4   1   3   3  
Diff:   4   0   1   0  

👀 Các phần tử có diff = 0 tạo thành good pairs, còn lại là bad pairs.

🎯 Final Thoughts

🔥 Đây là một bài toán thú vị với cách tiếp cận hash map + toán học giúp giảm độ phức tạp từ O(n²) ➝ O(n)!

📌 Những điều quan trọng rút ra từ bài này:

✅ Biến đổi điều kiện bài toán để nhận ra các phần tử giống nhau có thể nhóm lại.
✅ Sử dụng hash map để đếm nhanh số lần xuất hiện.
✅ Hiểu công thức tổ hợp giúp tính nhanh số lượng cặp có thể có.

📝 Bạn có thể áp dụng kỹ thuật này cho nhiều bài toán liên quan đến counting pairs!

💬 Bạn có thích cách tiếp cận này không? Hãy để lại bình luận nhé! 🚀

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