Today’s problem

https://leetcode.com/problems/count-number-of-bad-pairs/description/

Intuition

In this question, we find that we need to find the pairs that has the same distance as the difference of nums.

In this case, if we distract the distance between these two numbers, then they would be the same.

That is: $j - i = nums[j] - nums[i] \Longrightarrow nums[j] - j = nums[i] = i$.

Then the question would be easy: we just subtract the index of every number in the list, and then found how many pairs of i,j in the nums array that has the same number.

We then subtract these counts from the total counts of answer.

Approach

  1. Count all pairs of i,j; that is, $N \times (N - 1)$, N is the length of the array.
  2. Subtract all the nums[i] by i.
  3. Count how many pairs of i,j has the same number.
  4. Subtract these i,j pairs from the original answer.

Complexity

  • Time complexity: $O(N)$. N is the length of the array.

  • Space complexity: $O(N)$. N is the length of the array.

Code

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        nums = [nums[i] - i for i in range(len(nums))]
        cnt = Counter(nums)
        N = len(nums)
        ans = N * (N - 1) // 2
        for v in cnt.values():
            ans -= v * (v - 1) // 2

        return ans

image.png