Given an array of integers nums, a pair (i, j) is called a good pair if nums[i] == nums[j] and i < j. Return the number of good pairs.

  • Input: An array of integers nums.

  • Constraints:

    • 1 <= nums.length <= 100
    • 1 <= nums[i] <= 100

  • Output: An integer representing the total count of good pairs.

  • Example: Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: The good pairs are (0,3), (0,4), (3,4), (2,5).

    nums[0] == nums[3] (1 == 1)
nums[0] == nums[4] (1 == 1)
nums[3] == nums[4] (1 == 1)
nums[2] == nums[5] (3 == 3)

Solution

The problem asks us to find pairs (i, j) where nums[i] == nums[j] and i < j.

  • Optimized Approach (using a frequency map):
    • We can count the occurrences of each unique number in the nums array.
    • For a number that appears k times, the number of good pairs it forms is k * (k - 1) / 2. This is the combination formula "k choose 2", representing the number of ways to pick 2 distinct indices from k available indices.
    • Use a hash map (or a frequency array since nums[i] values are small) to store the counts of each number.
    • Iterate through the nums array to populate the frequency map.
    • After counting, iterate through the values (counts) in the frequency map. For each count k, add k * (k - 1) / 2 to a running total.
    • Time Complexity: O(n), where n is the length of nums. We iterate through nums once to count frequencies and then iterate through the map (at most max(nums[i]) or n unique elements) once to calculate pairs.
    • Space Complexity: O(U), where U is the number of unique elements in nums (at most max(nums[i]) or n).
class Solution:
    def numIdenticalPairs(self, nums: list[int]) -> int:
        good_pairs_count = 0
        freq_map = {}

        # Count frequencies of each number
        for num in nums:
            freq_map[num] = freq_map.get(num, 0) + 1

        # Calculate good pairs from frequencies
        for num_count in freq_map.values():
            if num_count >= 2:
                # If a number appears k times, it forms k * (k - 1) / 2 good pairs.
                good_pairs_count += (num_count * (num_count - 1)) // 2

        return good_pairs_count