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
- Counting bad pairs directly is awkward, but the complement is easy: a pair is good when
j - i == nums[j] - nums[i]. - Rearrange the good condition:
nums[i] - i == nums[j] - j. So group indices by the keynums[i] - i. - A group of size
ccontributesC(c, 2)good pairs. - The answer is the total number of pairs
n * (n - 1) / 2minus 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, notnums[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^5gives 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.