##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2364.html

# 2364. Count Number of Bad Pairs

• Difficulty: Medium.
• Related Topics: Array, Hash Table.
• Similar Questions: K-diff Pairs in an Array, Subarray Sums Divisible by K, Count Nice Pairs in an Array, Count Number of Pairs With Absolute Difference K, Count Equal and Divisible Pairs in an Array.

## 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

## Solution (Java, C++, Python)

• class Solution {
HashMap<Integer, Integer> seen = new HashMap<>();
long count = 0;
for (int i = 0; i < nums.length; i++) {
int diff = i - nums[i];
if (seen.containsKey(diff)) {
count += (i - seen.get(diff));
} else {
count += i;
}
seen.put(diff, seen.getOrDefault(diff, 0) + 1);
}
return count;
}
}

############

class Solution {
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;
}
}

• class Solution:
def countBadPairs(self, nums: List[int]) -> int:
arr = [i - v for i, v in enumerate(nums)]
cnt = Counter(arr)
n = len(arr)
return sum(v * (n - v) for v in cnt.values()) >> 1

############

# 2364. Count Number of Bad Pairs

class Solution:
def countBadPairs(self, nums: List[int]) -> int:
n = len(nums)
total = n * (n - 1) // 2
good = 0

mp = defaultdict(int)
# j - i != nums[j] - nums[i]
# Bad = j - nums[j] != i - nums[i]

for i, x in enumerate(nums):
good += mp[x - i]
mp[x - i] += 1


• class Solution {
public:
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;
}
};

• func countBadPairs(nums []int) (ans int64) {
cnt := map[int]int{}
for i, x := range nums {
x = i - x
ans += int64(i - cnt[x])
cnt[x]++
}
return
}

• function countBadPairs(nums: number[]): number {
const cnt = new Map<number, number>();
let ans = 0;
for (let i = 0; i < nums.length; ++i) {
const x = i - nums[i];
ans += i - (cnt.get(x) ?? 0);
cnt.set(x, (cnt.get(x) ?? 0) + 1);
}
return ans;
}



Explain:

nope.

Complexity:

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