2364. Count Number of Bad Pairs

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/count-number-of-bad-pairs
• topics: Mathematics, Hash Table

Description

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.

Idea

• Observe that j - i != nums[j] - nums[i] => j - nums[j] = i - nums[i]
• Count good pairs
• Answer = Total nbr of pairs - good pairs

Code

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        good_pairs = [v for k,v in 
            Counter(t - i for i, t in enumerate(nums)).items() if v > 1]
        ans = len(nums) * (len(nums) - 1) // 2 - sum(t * (t-1) // 2 for t in good_pairs)
        return ans