💬 Discord
Sign In
NeetCode #66LC-1512EasyArrays & Hashing
← Back to All Problems

#66 · #1512 · Number of Good Pairs(好数对的数目)

📌 Problem Statement & Constraints

Given an array of integers nums, return the number of good pairs (i, j) with i < j and nums[i] == nums[j]. Constraints: 1 <= nums.length <= 100, 1 <= nums[i] <= 100.

💡 Core Algorithmic Approaches

  1. Group the elements by value. If a value occurs c times, it contributes C(c, 2) = c * (c - 1) / 2 good pairs.
  2. Sum this over all distinct values.
  3. An incremental alternative: iterate the array once, and for each element add the number of previous occurrences to the answer, then increment its count.
  4. The incremental version avoids the combinatorial formula and is equally O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        from collections import Counter
        return sum(c * (c - 1) // 2 for c in Counter(nums).values())


# Incremental variant: count previous occurrences on the fly
class Solution2:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        from collections import defaultdict
        seen = defaultdict(int)
        res = 0
        for x in nums:
            res += seen[x]          # each previous occurrence forms one pair
            seen[x] += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to count, or one pass for the incremental variant.
💾 Space Complexity
O(k) for the frequency map, k <= 100 given the value range.

⚠️ Interview Pitfalls & Follow-ups

  • Using c * (c - 1) without dividing by 2: pairs are unordered, so the combination formula is required.
  • Counting ordered pairs (i, j) and (j, i) separately: the constraint is i < j.
  • Writing an O(n^2) double loop: correct but unnecessary; the counting approach is linear.