⚡Flashcard Drill➔
NeetCode #153LC-2364MediumArrays & Hashing
← Back to All Problems

#153 · #2364 · Count Number of Bad Pairs(统计坏数对的数目)

📌 Problem Statement & Constraints

You are given a 0-indexed integer array nums. A pair (i, j) is bad if i < j and j - i != nums[j] - nums[i]. Return the total number of bad pairs. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. Counting bad pairs directly is awkward, but the complement is easy: a pair is good when j - i == nums[j] - nums[i].
  2. Rearrange the good condition: nums[i] - i == nums[j] - j. So group indices by the key nums[i] - i.
  3. A group of size c contributes C(c, 2) good pairs.
  4. The answer is the total number of pairs n * (n - 1) / 2 minus the good pairs.

💻 Benchmark Python3 Implementation

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        from collections import Counter
        n = len(nums)
        total = n * (n - 1) // 2
        # good pairs: equal values of (nums[i] - i)
        cnt = Counter(nums[i] - i for i in range(n))
        good = sum(c * (c - 1) // 2 for c in cnt.values())
        return total - good

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to build the key counts.
💾 Space Complexity
O(n) for the counter.

⚠️ Interview Pitfalls & Follow-ups

  • Counting bad pairs directly with a double loop: O(n^2), far too slow at 10^5.
  • Using the wrong key: the condition is nums[i] - i == nums[j] - j, not nums[i] + i.
  • Forgetting to subtract from the total: the grouping counts good pairs, and the answer is the complement.
  • Assuming the answer fits in 32 bits: n = 10^5 gives about 5 * 10^9 pairs, so a 64-bit type (or Python's unbounded int) is required.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems