Number of Good Pairs

How it works

Instead of counting all frequencies first and then computing pairs, we can count pairs on the fly. As we traverse the array, each new occurrence of a value can form a good pair with every previous occurrence of that same value. We track the count of each value seen so far and add it to the res before updating the count.

Steps

1. Initialize a hash map to store the count of each number seen so far.
2. For each number in the array:
   • Add the current count of that number to the res (this is the number of new pairs formed).
   • Increment the count of that number in the map.
3. Return the res.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Double Counting Pairs

A good pair requires i < j, meaning each pair should only be counted once. When using nested loops, ensure the inner loop starts from i + 1 rather than 0. Similarly, when using the mathematical formula c * (c - 1) / 2, this already accounts for unique pairs and should not be doubled.

Integer Overflow in Pair Calculation

When using the formula c * (c - 1) / 2 to calculate the number of pairs for a frequency c, the multiplication can overflow for large values if using 32-bit integers. In languages with fixed-size integers, ensure you use an appropriate data type or perform the division before the multiplication becomes too large.

from typing import List
from collections import defaultdict

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        count = defaultdict(int)
        res = 0
        for num in nums:
            res += count[num]
            count[num] += 1
        return res

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int, int> count;
        int res = 0;
        for (int num : nums) {
            res += count[num];
            count[num]++;
        }
        return res;
    }
};