Skip to content

← leetcode

Count Number of Bad Pairs

· Medium

LeetCode problem 2364

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

  • Time: O(n)
  • Space: O(n)