# Count Number of Bad Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-number-of-bad-pairs)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-bad-pairs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
You are given a **0-indexed** integer array `nums`. A pair of indices `(i, j)` is a **bad pair** if `i < j` and `j - i != nums[j] - nums[i]`.

Return _the total number of **bad pairs** in_ `nums`.

**Example 1:**

**Input:** nums = [4,1,3,3]
**Output:** 5
**Explanation:** The pair (0, 1) is a bad pair since 1 - 0 != 1 - 4.
The pair (0, 2) is a bad pair since 2 - 0 != 3 - 4, 2 != -1.
The pair (0, 3) is a bad pair since 3 - 0 != 3 - 4, 3 != -1.
The pair (1, 2) is a bad pair since 2 - 1 != 3 - 1, 1 != 2.
The pair (2, 3) is a bad pair since 3 - 2 != 3 - 3, 1 != 0.
There are a total of 5 bad pairs, so we return 5.

**Example 2:**

**Input:** nums = [1,2,3,4,5]
**Output:** 0
**Explanation:** There are no bad pairs.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force Iteration
The most straightforward approach is to check every possible pair of indices `(i, j)` where `i < j`. For each pair, we directly evaluate the condition `j - i != nums[j] - nums[i]`. If the condition holds true, we increment a counter for bad pairs.
**Time:** O(n^2), where n is the number of elements in `nums`. We use nested loops to check every possible pair `(i, j)` with `i < j`, which amounts to `n * (n - 1) / 2` checks. · **Space:** O(1), as we only use a constant amount of extra space for loop variables and the counter.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Highly inefficient for the given constraints (n <= 10^5), leading to a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
This method uses a nested loop structure to generate all unique pairs of indices `(i, j)` with `i < j`. The outer loop runs from `i = 0` to `n-2`, and the inner loop runs from `j = i + 1` to `n-1`. Inside the inner loop, we perform the check `j - i != nums[j] - nums[i]`. A running counter, initialized to zero, is incremented each time we find such a 'bad pair'. The final value of this counter is the result. Note that the count can exceed the capacity of a 32-bit integer, so a `long` should be used for the counter.

```java
class Solution {
    public long countBadPairs(int[] nums) {
        long badPairsCount = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // The condition for a bad pair
                if ((long)j - i != (long)nums[j] - nums[i]) {
                    badPairsCount++;
                }
            }
        }
        return badPairsCount;
    }
}
```
### Algorithm
- Initialize a counter `badPairsCount` to 0.
- Get the length of the array, `n`.
- Use a nested loop:
  - The outer loop iterates `i` from `0` to `n-2`.
  - The inner loop iterates `j` from `i+1` to `n-1`.
- Inside the inner loop, check the condition: `if (j - i != nums[j] - nums[i])`.
- If the condition is true, increment `badPairsCount`.
- After the loops complete, return `badPairsCount`.

## Optimized Approach using Hash Map and Counting Good Pairs
A more efficient approach is to count the number of 'good pairs' and subtract this from the total number of pairs. A pair `(i, j)` is 'good' if `i < j` and `j - i == nums[j] - nums[i]`. This condition can be rearranged to `nums[i] - i == nums[j] - j`. This insight transforms the problem into finding pairs of indices `(i, j)` that have the same value for the expression `nums[k] - k`. This can be solved efficiently in a single pass using a hash map to store the frequencies of these values.
**Time:** O(n), where n is the number of elements in `nums`. We iterate through the array once, and each hash map operation (get, put) takes O(1) time on average. · **Space:** O(n) in the worst case. The hash map might need to store up to `n` distinct key-value pairs if all `nums[i] - i` values are unique.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Solves the problem in a single pass through the array.
**Cons:** Requires extra space for the hash map, which can be up to O(n) in the worst case.; The logic is less direct than the brute-force approach due to the mathematical rearrangement of the condition.
### Explanation
First, we recognize that `Total Pairs = Good Pairs + Bad Pairs`. The total number of pairs `(i, j)` with `i < j` in an array of length `n` is `n * (n - 1) / 2`. We can find the number of bad pairs by calculating `Total Pairs - Good Pairs`.

The condition for a good pair, `nums[i] - i == nums[j] - j`, means we need to count how many pairs of indices have an equal `nums[k] - k` value. We can do this in one pass. We iterate through the array, and for each element `nums[i]`, we calculate `diff = nums[i] - i`. We use a hash map to keep track of the frequencies of these `diff` values encountered so far. For the current `i`, the number of good pairs it forms with elements at indices `j < i` is exactly the number of times we have already seen the value `diff`. We add this count to our `goodPairs` total and then update the map with the `diff` from the current element.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long countBadPairs(int[] nums) {
        int n = nums.length;
        long goodPairs = 0;
        // Map to store frequency of (nums[i] - i)
        Map<Integer, Integer> freq = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            int diff = nums[i] - i;
            // The number of good pairs ending at index i is the number of times
            // we've seen the same 'diff' value before.
            goodPairs += freq.getOrDefault(diff, 0);
            
            // Increment the frequency of the current 'diff' value.
            freq.put(diff, freq.getOrDefault(diff, 0) + 1);
        }
        
        // Total number of pairs is n * (n - 1) / 2
        long totalPairs = (long)n * (n - 1) / 2;
        
        // Bad pairs = Total pairs - Good pairs
        return totalPairs - goodPairs;
    }
}
```
### Algorithm
- The total number of pairs `(i, j)` with `i < j` is `total_pairs = n * (n - 1) / 2`.
- The number of bad pairs is `total_pairs - good_pairs`.
- A pair is 'good' if `j - i == nums[j] - nums[i]`, which can be rearranged to `nums[i] - i == nums[j] - j`.
- We can count good pairs efficiently:
  - Initialize `good_pairs_count = 0` and a hash map `freq_map`.
  - Iterate through the array `nums` from `i = 0` to `n-1`.
  - For each element, calculate `diff = nums[i] - i`.
  - The number of previous elements that form a good pair with the current element is the current frequency of `diff` in `freq_map`. Add this frequency to `good_pairs_count`.
  - Increment the frequency of `diff` in `freq_map`.
- Finally, return `total_pairs - good_pairs_count`.

# Solutions
### Java

```java
class Solution {
public
  long countBadPairs(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    long ans = 0;
    for (int i = 0; i < nums.length; ++i) {
      int x = i - nums[i];
      ans += i - cnt.getOrDefault(x, 0);
      cnt.merge(x, 1, Integer : : sum);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countBadPairs(vector<int> &nums) {
    unordered_map<int, int> cnt;
    long long ans = 0;
    for (int i = 0; i < nums.size(); ++i) {
      int x = i - nums[i];
      ans += i - cnt[x];
      ++cnt[x];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countBadPairs(self, nums: List[int]) -> int: cnt = Counter() ans = 0 for i, x in enumerate(nums): ans += i - cnt[i - x] cnt[i - x] += 1 return ans

```