Code Implementation

class Solution:
    def numIdenticalPairs(self, nums):
        from collections import defaultdict
        count = defaultdict(int)
        good_pairs = 0
        for num in nums:
            good_pairs += count[num]
            count[num] += 1
        return good_pairs
      

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

class Solution {
    public int numIdenticalPairs(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        int goodPairs = 0;
        for (int num : nums) {
            goodPairs += count.getOrDefault(num, 0);
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        return goodPairs;
    }
}
      

var numIdenticalPairs = function(nums) {
    let count = {};
    let goodPairs = 0;
    for (let num of nums) {
        goodPairs += (count[num] || 0);
        count[num] = (count[num] || 0) + 1;
    }
    return goodPairs;
};
      

Problem Description

You are given an array of integers called nums. Your task is to count the number of good pairs in the array. A good pair is defined as a pair of indices (i, j) where i < j and nums[i] == nums[j].

Key constraints:

• Each pair must use two different indices; you cannot reuse the same element twice in a pair.
• Order matters: i must be less than j.
• There may be multiple good pairs for the same value if it appears more than twice.

Thought Process

At first glance, the problem seems to suggest checking every possible pair of indices in nums and counting those where the elements are equal. This would involve two nested loops, comparing each pair (i, j) where i < j. While this works for small arrays, it quickly becomes inefficient as the array grows.

Thinking further, we realize that for each number, the number of good pairs it contributes depends on how many times it has appeared so far. For each new occurrence, it forms a new good pair with each of its previous occurrences. This insight allows us to use a frequency counter (hash map) to keep track of how many times we've seen each value as we iterate.

This optimization shifts our approach from brute-force (comparing all pairs) to a single pass using a hash map, making the solution much faster and more efficient.

Solution Approach

• Step 1: Initialize a hash map (dictionary) to keep track of how many times each number has appeared so far.
• Step 2: Initialize a variable good_pairs to 0. This will store our running total of good pairs.
• Step 3: Iterate through the array nums from left to right.
• Step 4: For each element num at index i:
  • Add the current count of num (from the hash map) to good_pairs. This counts all good pairs that can be formed with previous occurrences of num.
  • Increment the count of num in the hash map by 1.
• Step 5: After finishing the loop, return the value of good_pairs.

This approach works efficiently because looking up and updating the hash map is a constant-time operation, and we only need to loop through the array once.

Example Walkthrough

Let's use the sample input: nums = [1,2,3,1,1,3]

• Start with an empty hash map and good_pairs = 0.
• Index 0: num = 1. Hash map: {1: 0}. Add 0 to good_pairs (still 0). Update hash map: {1: 1}.
• Index 1: num = 2. Hash map: {1: 1, 2: 0}. Add 0 to good_pairs (still 0). Update: {1:1, 2:1}.
• Index 2: num = 3. Hash map: {1:1, 2:1, 3:0}. Add 0 to good_pairs (still 0). Update: {1:1, 2:1, 3:1}.
• Index 3: num = 1. Hash map: {1:1, 2:1, 3:1}. Add 1 to good_pairs (now 1). Update: {1:2, 2:1, 3:1}.
• Index 4: num = 1. Hash map: {1:2, 2:1, 3:1}. Add 2 to good_pairs (now 3). Update: {1:3, 2:1, 3:1}.
• Index 5: num = 3. Hash map: {1:3, 2:1, 3:1}. Add 1 to good_pairs (now 4). Update: {1:3, 2:1, 3:2}.

The final answer is 4, which matches the number of good pairs: (0,3), (0,4), (3,4), and (2,5).

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n^2) because it checks every possible pair.
  • Space Complexity: O(1) extra space, aside from the input.
• Optimized hash map approach:
  • Time Complexity: O(n), since we only loop through the array once and each hash map operation is O(1).
  • Space Complexity: O(n), in the worst case where all elements are unique and we store each in the hash map.

The optimized approach is much better for large arrays and is the preferred solution.

Summary

To solve the "Number of Good Pairs" problem, we count how many times each number has appeared as we traverse the array. For each new occurrence, we add the number of previous occurrences to our result. This simple use of a hash map allows us to avoid checking every pair and gives us an efficient, elegant solution.