Problem Description

You are given an array of integers called nums. Your task is to count the number of good pairs in this array.

A pair of indices (i, j) is considered a good pair if it satisfies two conditions:

1. The values at these indices are equal: nums[i] == nums[j]
2. The first index comes before the second index: i < j

For example, if nums = [1, 2, 3, 1, 1, 3]:

• Indices (0, 3) form a good pair because nums[0] = nums[3] = 1 and 0 < 3
• Indices (0, 4) form a good pair because nums[0] = nums[4] = 1 and 0 < 4
• Indices (3, 4) form a good pair because nums[3] = nums[4] = 1 and 3 < 4
• Indices (2, 5) form a good pair because nums[2] = nums[5] = 3 and 2 < 5

The solution uses a counting approach. As we traverse the array from left to right, for each element x, we check how many times we've seen x before. Each previous occurrence of x can form a good pair with the current x. We keep track of the count of each element using a Counter (hash map), and for each element, we add the current count to our answer before incrementing the count.

This way, if we encounter the same value multiple times, we automatically count all valid pairs where the current position serves as the second index j and all previous occurrences serve as the first index i.

Intuition

The key insight is that when we encounter an element at position j, we need to count how many times this same element appeared at positions before j (all valid i where i < j). Each of those previous occurrences forms a good pair with the current element.

Think about it this way: if we're at position j and we see value x, and we know that x appeared k times before position j, then we can form exactly k good pairs with the current element as the second element of each pair.

For example, if we have [1, 1, 1]:

• When we see the first 1 at index 0, there are 0 previous 1s, so 0 pairs
• When we see the second 1 at index 1, there is 1 previous 1 (at index 0), so 1 pair: (0,1)
• When we see the third 1 at index 2, there are 2 previous 1s (at indices 0 and 1), so 2 pairs: (0,2) and (1,2)
• Total: 0 + 1 + 2 = 3 pairs

This pattern suggests we can solve the problem in a single pass through the array. We maintain a count of how many times we've seen each value so far. When we encounter a value, we:

1. Add the current count of that value to our answer (these are all the good pairs we can form with previous occurrences)
2. Increment the count for that value (for future elements to reference)

This approach is efficient because we only need to traverse the array once, and each operation (looking up and updating the count) takes constant time using a hash map.

Learn more about Math patterns.

Solution Approach

The solution implements a counting approach using a hash map to track occurrences of each element as we traverse the array.

Algorithm Steps:

1. Initialize a counter variable ans to 0 to store the total number of good pairs
2. Create an empty Counter (hash map) cnt to track the frequency of each element seen so far
3. Traverse through each element x in the array:
   • Add cnt[x] to the answer - this represents the number of good pairs that can be formed with x as the second element and all previous occurrences of x as the first element
   • Increment cnt[x] by 1 to update the count for future iterations

Why this works:

When processing element at index j with value x:

• cnt[x] tells us how many times x appeared at indices i where i < j
• Each of these previous occurrences forms a valid good pair (i, j) since nums[i] == nums[j] == x and i < j
• After counting the pairs, we increment cnt[x] so that when we encounter x again at a future index, it can form pairs with this current occurrence

Example walkthrough with nums = [1, 2, 3, 1, 1, 3]:

• Index 0, x = 1: cnt[1] = 0, add 0 to ans, update cnt[1] = 1
• Index 1, x = 2: cnt[2] = 0, add 0 to ans, update cnt[2] = 1
• Index 2, x = 3: cnt[3] = 0, add 0 to ans, update cnt[3] = 1
• Index 3, x = 1: cnt[1] = 1, add 1 to ans, update cnt[1] = 2
• Index 4, x = 1: cnt[1] = 2, add 2 to ans, update cnt[1] = 3
• Index 5, x = 3: cnt[3] = 1, add 1 to ans, update cnt[3] = 2
• Total: 0 + 0 + 0 + 1 + 2 + 1 = 4

Time Complexity: O(n) where n is the length of the array - single pass through the array
Space Complexity: O(k) where k is the number of unique elements in the array

Example Walkthrough

Let's walk through a simple example with nums = [1, 1, 1, 2, 1] to illustrate how the counting approach works.

Initial State:

• ans = 0 (total good pairs count)
• cnt = {} (empty counter/hash map)

Step-by-step Processing:

Index 0: value = 1

• Check cnt[1] → 0 (no previous 1's seen)
• Add 0 to ans: ans = 0 + 0 = 0
• Update counter: cnt[1] = 1
• State: cnt = {1: 1}, ans = 0

Index 1: value = 1

• Check cnt[1] → 1 (one previous 1 at index 0)
• This forms 1 good pair: (0, 1)
• Add 1 to ans: ans = 0 + 1 = 1
• Update counter: cnt[1] = 2
• State: cnt = {1: 2}, ans = 1

Index 2: value = 1

• Check cnt[1] → 2 (two previous 1's at indices 0 and 1)
• This forms 2 good pairs: (0, 2) and (1, 2)
• Add 2 to ans: ans = 1 + 2 = 3
• Update counter: cnt[1] = 3
• State: cnt = {1: 3}, ans = 3

Index 3: value = 2

• Check cnt[2] → 0 (no previous 2's seen)
• Add 0 to ans: ans = 3 + 0 = 3
• Update counter: cnt[2] = 1
• State: cnt = {1: 3, 2: 1}, ans = 3

Index 4: value = 1

• Check cnt[1] → 3 (three previous 1's at indices 0, 1, and 2)
• This forms 3 good pairs: (0, 4), (1, 4), and (2, 4)
• Add 3 to ans: ans = 3 + 3 = 6
• Update counter: cnt[1] = 4
• State: cnt = {1: 4, 2: 1}, ans = 6

Final Answer: 6 good pairs

The good pairs are: (0,1), (0,2), (1,2), (0,4), (1,4), (2,4)

Notice how at each step, the counter tells us exactly how many good pairs we can form with the current element as the second element of the pair.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the input array nums. The algorithm iterates through the array exactly once, and for each element, it performs constant-time operations: accessing the counter value, incrementing the answer, and updating the counter.

The space complexity is O(C), where C represents the number of unique elements in the array. In the worst case, this could be O(n) if all elements are unique. However, given the problem constraints where array values are bounded (typically between 1 and 100 for this LeetCode problem), we can say the space complexity is O(101) or simply O(1) since it's bounded by a constant. The Counter dictionary stores at most C key-value pairs, where C = 101 based on the value range constraint.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using Nested Loops (Brute Force Approach)

A common mistake is implementing a brute force solution with nested loops to check all possible pairs:

def numIdenticalPairs(self, nums: List[int]) -> int:
    count = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                count += 1
    return count

Why it's problematic: This approach has O(n²) time complexity, which becomes inefficient for large arrays.

Solution: Use the counting approach shown in the main solution to achieve O(n) time complexity.

Pitfall 2: Incorrectly Counting Pairs Multiple Times

Some might try to count all occurrences at once after building the frequency map:

def numIdenticalPairs(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    count = 0
    for freq in frequency_map.values():
        # Trying to calculate all pairs at once
        count += freq * (freq - 1) // 2
    return count

While this actually works correctly (using the combination formula), it requires understanding the mathematical relationship and can be less intuitive.

Solution: The incremental counting approach in the main solution is more intuitive and easier to understand - we count pairs as we encounter each element.

Pitfall 3: Forgetting to Update Counter After Using It

A subtle bug can occur if you increment the counter before adding to the answer:

def numIdenticalPairs(self, nums: List[int]) -> int:
    good_pairs_count = 0
    frequency_map = Counter()
  
    for num in nums:
        frequency_map[num] += 1  # Incrementing BEFORE counting pairs
        good_pairs_count += frequency_map[num] - 1  # Now need to subtract 1
  
    return good_pairs_count

Why it's problematic: This makes the logic less clear and more error-prone. You need to remember to subtract 1 because you've already included the current element in the count.

Solution: Always add the current count first, then increment. This maintains the clear logic that frequency_map[num] represents the number of previous occurrences that can form pairs with the current element.

Pitfall 4: Using a Regular Dictionary Without Proper Initialization

Using a regular dict instead of Counter without proper key checking:

def numIdenticalPairs(self, nums: List[int]) -> int:
    good_pairs_count = 0
    frequency_map = {}
  
    for num in nums:
        good_pairs_count += frequency_map[num]  # KeyError if num not in dict!
        frequency_map[num] += 1  # Another KeyError!
  
    return good_pairs_count

Solution: Either use Counter() which handles missing keys gracefully, or properly check/initialize keys:

def numIdenticalPairs(self, nums: List[int]) -> int:
    good_pairs_count = 0
    frequency_map = {}
  
    for num in nums:
        good_pairs_count += frequency_map.get(num, 0)
        frequency_map[num] = frequency_map.get(num, 0) + 1
  
    return good_pairs_count