LeetCode 1512: Number of Good Pairs Solution in Python

Task (Problem Instructions)

LeetCode problem 1512, titled “Number of Good Pairs,” involves calculating the number of pairs of indices (i, j) in a given array such that i < j and the elements at these indices are equal, nums[i] == nums[j]. The input is an array of integers, and the output is an integer representing the total count of such pairs. This problem tests understanding of array manipulation and the ability to count specific configurations within an array.

The problem can also be framed as a Combinations challenge, solvable by employing a HashMap to tally the frequency of identical values. This approach leverages the concept of counting the number of unique pairs (combinations) that can be formed from n items when the order is not significant. Specifically, it is possible to count each item pairing with (n-1) others without utilizing Python’s math.comb() function. Given that each pair is counted twice because the order of elements is irrelevant, the total count of pairs, n * (n-1), is halved, leading to the formula n * (n-1) / 2. This division adjusts for the double-counting, providing an accurate count of unique pairs.

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
      m = defaultdict(int)
      # Count appearances for each number
      for n in nums:
        m[n] += 1
      
      combinations = 0

      '''The order doesn't matter, thus we can use n*(n-1)/2 formula instead of Python's math.comb() function, to maintain a linear time complexity.'''
      for count in m.values():
        combinations += count * (count - 1) // 2
      
      return combinations

Solution Logic Explained

My Number of Good Pairs LeetCode solution starts by creating a default dictionary, m, where each key-value pair represents a numeric value from the array and its frequency of appearance, respectively. The defaultdict(int) ensures that any new key is initialized with a value of 0.

The code iterates over each number n in the input array nums. For every iteration, it increments the count of n in the dictionary m. This loop effectively counts the frequency of each unique number in the array.

After populating the dictionary with the frequencies of each number, the solution then initializes a variable, combinations, to 0. This variable will accumulate the total number of good pairs.

The code iterates over the values of the dictionary m (i.e., the counts of each number). For each count, it calculates the number of unique pairs that can be formed using the formula count * (count - 1) // 2. This formula is derived from the combination formula for selecting 2 items out of n, without considering the order (i.e., nC2), but optimized to avoid the need for a factorial calculation, thus maintaining linear time complexity.

Adding Combinations

For each frequency count, the code calculates the number of pairs and adds this to the combinations variable. This step is based on the mathematical fact that a number appearing n times can form n*(n-1)/2 unique pairs with itself, as order does not matter, and each pair is counted once.

Finally, the function returns the total count of combinations, which represents the number of good pairs in the input array.

Complexity Analysis

Time complexity: This approach is efficient, with a time complexity of O(N), where N is the length of the input array. It avoids quadratic time complexity by not explicitly searching for pairs but rather calculating the number of pairs directly from the counts of each number.

Space complexity: The (auxiliary) space complexity of the discussed solution for the “Number of Good Pairs” LeetCode problem hinges on the HashMap (default dictionary) used to tally the frequencies of each unique number within the input array. This complexity is O(U), with U symbolizing the count of unique elements present in the array. In scenarios where each element in the array is distinct, the space complexity escalates to O(N), where N signifies the total number of items in the array. This estimation specifically accounts for the additional memory necessitated by the HashMap.

Overall, this solution is a decent demonstration of how understanding mathematical properties and data structure utilization can lead to efficient algorithms for seemingly complex problems.