5 Best Ways to Find the Number of Good Pairs in Python

Rate this post

πŸ’‘ Problem Formulation: A ‘good pair’ in an array is a pair of indices (i, j), where i < j, with equal array values. Given an array of integers, the goal is to count the number of good pairs. For instance, in the array [1, 2, 3, 1, 1, 3], there are four good pairs: (0, 3), (0, 4), (3, 4), and (2, 5).

Method 1: Brute Force

The brute force method to find the number of good pairs involves checking all possible pairs in the array. This method iterates over each element and compares it to the subsequent elements to count pairs with equal values.

Here’s an example:

def count_good_pairs(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                count += 1
    return count

print(count_good_pairs([1, 2, 3, 1, 1, 3]))

Output: 4

This code uses two nested loops to iterate over the array and increment the count whenever a good pair is found, i.e., when two elements have the same value and the first index is less than the second index.

Method 2: Hashing with Counts

Hashing with counts streamlines the process by storing the frequency of each element in a dictionary. The number of good pairs can be calculated using the formula n(n-1)/2 for each element, where ‘n’ is the frequency of that element.

Here’s an example:

from collections import Counter

def count_good_pairs(nums):
    freq = Counter(nums)
    return sum(k * (k - 1) // 2 for k in freq.values())

print(count_good_pairs([1, 2, 3, 1, 1, 3]))

Output: 4

This snippet uses the Counter class from collections to count occurrences of each number. Then, it calculates the total number of good pairs by applying the combination formula to each count.

Method 3: Hashing with Incremental Updates

This efficiency-oriented approach uses a hash map to perform incremental updates. As we iterate through the array, we increment the count of good pairs by the current frequency of the element before updating its frequency.

Here’s an example:

def count_good_pairs(nums):
    freq = {}
    count = 0
    for num in nums:
        if num in freq:
            count += freq[num]
            freq[num] += 1
        else:
            freq[num] = 1
    return count

print(count_good_pairs([1, 2, 3, 1, 1, 3]))

Output: 4

Each time a number appears, the increment in the count reflects the number of good pairs that can be formed with that number, exploiting the fact that a new pair is formed for each previous occurrence of the same number.

Method 4: Using Combinations from itertools

Python’s itertools library provides a combinations function that can generate all possible pairs, which we can then filter to count only the good ones. This method hides the complexity of pairwise comparisons behind a library function.

Here’s an example:

from itertools import combinations

def count_good_pairs(nums):
    return sum(1 for a, b in combinations(nums, 2) if a == b)

print(count_good_pairs([1, 2, 3, 1, 1, 3]))

Output: 4

By calling combinations(nums, 2), we generate all possible pairs without repetition. We then iterate through these pairs and count those with equal values.

Bonus One-Liner Method 5: List Comprehension with Enumerate

This one-liner approach uses a list comprehension in combination with enumerate to compactly express the process of counting good pairs. It is a Pythonic way to write a loop in a single line.

Here’s an example:

nums = [1, 2, 3, 1, 1, 3]
print(sum(1 for i, v in enumerate(nums) for j in range(i+1, len(nums)) if nums[j] == v))

Output: 4

In this code, enumerate splits the array into index-value pairs, and then a nested generator expression checks for equal values at different indices, directly counting the good pairs.

Summary/Discussion

  • Method 1: Brute Force. Straightforward and simple to understand. Inefficient for large lists due to its O(n^2) time complexity.
  • Method 2: Hashing with Counts. More efficient than brute force. Reduced time complexity to O(n). Requires additional space for the frequency dictionary.
  • Method 3: Hashing with Incremental Updates. Similar to Method 2 but updates the count during a single array traversal. Space complexity is reduced at the cost of slight code complexity.
  • Method 4: Using Combinations from itertools. Leverages built-in Python libraries for clean and concise code. The computational cost is equivalent to brute force if all combinations are generated.
  • Bonus Method 5: List Comprehension with Enumerate. Expressive and compact. Ideal for shorter lists but can be less readable and maintains O(n^2) complexity.