2364: Count-Number-of-Bad-Pairs
Medium 2025-02-09

I think seeing the vision trivialises the solution of this problem. The key trick to realise is that the condition j - i != nums[j] - nums[i] can be rearranged as j - nums[j] != i - nums[i].

Then, we can just use an unordered_map (hashmap) to track the count good pairs and subtract of the number of total pairs to get the number of bad pairs.

Note, that the number of total pairs is just (n-1) + (n-2) + ... + 2 + 1 = n * (n-1) / 2.

Code:

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        long long n = nums.size();
        long long ans = n * (n-1) / 2;

        unordered_map<int, long long> mp;
        long long good_pair_count = 0;
        for (int i = 0; i < n; ++i) {
            ++mp[i-nums[i]];
        }

        for (auto const& [key, value] : mp) {
            good_pair_count += value*(value-1)/2;
        }

        return ans - good_pair_count;
    }
};

Complexity: