Count Number of Bad Pairs — Editorial

Opening the reading…

Intuitionturning a pair condition into equal keys

The definition calls a pair good when j - i equals nums[j] - nums[i]. Rearrange that equation by moving i and nums[i] to the same side: nums[i] - i equals nums[j] - j. Therefore, two indices form a good pair exactly when they produce the same value of nums[index] - index.

Counting bad pairs directly would require checking every pair, which takes quadratic time. Instead, count the good pairs while scanning from left to right. When index i produces a key, every earlier index with that same key forms one good pair with i. The total number of index pairs is n x (n - 1) / 2, so subtracting the good count leaves the bad count.

Equal transformed keys identify the pairs that are not bad.

Approachcount the complement in one scan

Compute the total number of index pairs as n x (n - 1) / 2, because every choice of two distinct indices contributes one pair and the smaller index is automatically first.

Create a frequency map for values of nums[i] - i, because the rearranged equality says that this key is the only information needed to recognize a good pair.

Scan indices from left to right and compute key = nums[i] - i. Earlier indices are the only possible partners, so the current frequency already represents exactly the valid first endpoints.

Add freq[key] to the good-pair count, because each earlier occurrence of this key forms one new good pair with i; adding anything else would count pairs that do not satisfy the equation.

Increment freq[key] after counting the matches, so the current index is not paired with itself and becomes available only for later indices.

Return total - good. Every pair is either good or bad, and the two categories are disjoint, so subtracting the counted complement gives the required result.

Complexityexpected hashing cost and linear working memory

MEASURE	BOUND	WHY
Time	O(n) expected	The scan performs one map lookup and one map update per index. Hash-table operations take expected O(1), so the total work is proportional to the n indices; an unusually collision-heavy hash table can degrade individual operations.
Space	O(n) extra	The frequency map stores one entry for each distinct transformed key, at most one per index. It uses O(n) space when all keys differ and less space when many indices share a key; the returned count is output storage and is excluded.

Here n is the length of nums. The output value is a single integer and is excluded from extra space.

Annotated solutionC++ · one pass with a frequency map

CPPCount good pairs by transformed-key frequency, then subtract them from all pairs.

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        unordered_map<int, int> freq;
        long long good = 0;
        int n = nums.size();

        for (int i = 0; i < n; ++i) {
            int key = nums[i] - i;
            good += freq[key];
            ++freq[key];
        }

        long long total = static_cast<long long>(n) * (n - 1) / 2;
        return total - good;
    }
};

The order of the two map operations matters. Adding freq[key] before incrementing it counts only earlier indices, exactly matching i < j. The long long variables are also deliberate: with 100000 elements, the number of pairs is about five billion, which does not fit in a 32-bit signed int even though each array value and index do.