Problem of The Day: Count Number of Bad Pairs

Problem Statement

Brute Force [TLE]

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        N = len(nums)
        res = 0
        for i in range(N - 1):
            for j in range(i + 1, N):
                if j - i != nums[j] - nums[i]:
                    res += 1
        return res

Discussion Solution

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        d = defaultdict(int)
        good_pairs = 0
        for i in range(len(nums)):
            diff = nums[i] - i

            good_pairs += d[diff]

            d[diff] += 1

        n = len(nums)

        total_pairs = n * (n - 1) // 2

        return total_pairs - good_pairs

Editorial

Approach: Hash Map

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        bad_pairs = 0
        diff_count = {}

        for pos in range(len(nums)):
            diff = pos - nums[pos]

            # Count of previous positions with same difference
            good_pairs_count = diff_count.get(diff, 0)

            # Total possible pairs minus good pairs = bad pairs
            bad_pairs += pos - good_pairs_count

            # Update count of positions with this difference
            diff_count[diff] = good_pairs_count + 1

        return bad_pairs