Count Number of Bad Pairs
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 10 - ◆
-100 ≤ nums[i] ≤ 100
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Pair Directly
GoodA pair of indices (i, j) with i < j is bad when the gap between the indices doesn't match the gap between the values there — that is, j - i ≠ nums[j] - nums[i]. Check every pair directly against that condition and count how many fail it. Simple and correct, but checking all C(n, 2) pairs one at a time means the work grows with the square of the array size.
O(n²)O(1)1class Solution {
2 public int countBadPairs(int[] nums) {
3 int n = nums.length;
4 int count = 0;
5 for (int i = 0; i < n; i++) {
6 for (int j = i + 1; j < n; j++) {
7 if ((j - i) != (nums[j] - nums[i])) {
8 count++;
9 }
10 }
11 }
12 return count;
13 }
14}Optimal — Total Minus Good Pairs via HashMap
OptimalRearranging j - i ≠ nums[j] - nums[i] gives nums[j] - j ≠ nums[i] - i — a pair is GOOD exactly when nums[k] - k is the same for both indices. So instead of testing every pair, count how many indices share each value of nums[k] - k with a hash map; any group of c indices sharing a value contributes C(c, 2) good pairs. Sum those up across every group to get the total good-pair count, then subtract it from C(n, 2) (every possible pair) to get the number of bad pairs — all in a single pass plus one pass over the map.
O(n)O(n)1class Solution {
2 public int countBadPairs(int[] nums) {
3 int n = nums.length;
4 int total = n * (n - 1) / 2;
5 Map<Integer, Integer> diffCount = new HashMap<>();
6 for (int k = 0; k < n; k++) {
7 int d = nums[k] - k;
8 diffCount.merge(d, 1, Integer::sum);
9 }
10 int good = 0;
11 for (int c : diffCount.values()) {
12 good += c * (c - 1) / 2;
13 }
14 return total - good;
15 }
16}