algoadvance

LeetCode Problem 1512: Number of Good Pairs

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

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) because nums[0] == nums[3] == nums[4] and nums[2] == nums[5].

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array is good.

Example 3:

Input: nums = [1,2,3]
Output: 0

Clarifying Questions

  1. Can the array contain negative numbers or zeros?
    • Yes, as long as they are integers.
  2. Is the array sorted?
    • No, the array is not necessarily sorted.
  3. What is the maximum size of the input array?
    • The size of the input array can go up to 100.

Strategy

  1. Count Frequency: We can use a dictionary to count the frequency of each number in the array.
  2. Calculate Good Pairs: For each count of a number greater than 1, the number of good pairs can be determined using the combination formula C(n, 2) = n * (n - 1) / 2, where n is the count of that number.

Code

def numIdenticalPairs(nums):
    from collections import defaultdict
    
    # Dictionary to store the frequency of each number
    count_dict = defaultdict(int)
    
    # Count the frequency of each number in the array
    for num in nums:
        count_dict[num] += 1
    
    # Calculate the number of good pairs
    good_pairs = 0
    for count in count_dict.values():
        if count > 1:
            good_pairs += (count * (count - 1)) // 2
    
    return good_pairs

# Test Cases
print(numIdenticalPairs([1,2,3,1,1,3]))  # Output: 4
print(numIdenticalPairs([1,1,1,1]))      # Output: 6
print(numIdenticalPairs([1,2,3]))        # Output: 0

Time Complexity

The provided algorithm effectively calculates the number of good pairs with optimal time and space complexity for the given constraints.

Try our interview co-pilot at AlgoAdvance.com