Skip to content

2364. Count Number of Bad Pairs 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  long long countBadPairs(vector<int>& nums) {
    long ans = 0;
    unordered_map<int, int> count;  // (nums[i] - i)

    for (int i = 0; i < nums.size(); ++i)
      //     count[nums[i] - i] := the number of good pairs
      // i - count[nums[i] - i] := the number of bad pairs
      ans += i - count[nums[i] - i]++;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public long countBadPairs(int[] nums) {
    long ans = 0;
    Map<Integer, Long> count = new HashMap<>(); // (nums[i] - i)

    for (int i = 0; i < nums.length; ++i) {
      //     count[nums[i] - i] := the number of good pairs
      // i - count[nums[i] - i] := the number of bad pairs
      ans += i - count.getOrDefault(nums[i] - i, 0L);
      count.merge(nums[i] - i, 1L, Long::sum);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def countBadPairs(self, nums: list[int]) -> int:
    ans = 0
    count = collections.Counter()  # (nums[i] - i)

    for i, num in enumerate(nums):
      #     count[nums[i] - i] := the number of good pairs
      # i - count[nums[i] - i] := the number of bad pairs
      ans += i - count[num - i]
      count[num - i] += 1

    return ans