< Back




1512. Number of Good Pairs

A good pair is a good pair if some indices i and j satisfy the condition nums[i] == nums[j] and
i < j. We're asked to return the number of good pairs in the input array.

We can simply do this by maintaining a dictionary to keep track of the number of occurrences of each
integer. When we iterate through the list of numbers, we look to see if we've already encountered
this integer. If so, we add the current count to the answer and then increment the count.

This is because, if we've already seen the number, then we know that this current number would be
a good pair with all the previous occurrences of the number. The dictionary inherently keeps track of
the number of good pairs we've seen so far.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def numIdenticalPairs(self, nums: List[int]) -> int:
          counts = defaultdict(int)
          ans = 0

          for num in nums:
              ans += counts[num]
              counts[num] += 1

          return ans


_ Time Complexity:

  O(n) - We iterate through the input string once.

_ Space Complexity:

  O(n) - We maintain a running count for each integer encountered in the input list.