algoadvance

Given an array of integers nums, a pair (i, j) is called “good” if nums[i] == nums[j] and i < j. We need to count the number of good pairs.

Clarifying Questions

  1. What should be returned if there are no good pairs?
    • Return 0 if no good pairs are found.
  2. Can the array contain negative numbers and zero?
    • Yes, the array can contain any integer value.
  3. What is the range of the length of the array?
    • The array length can range from 1 to (10^5).
  4. Do we need to handle any specific edge cases?
    • Single element arrays or arrays with all unique elements would result in 0 good pairs.

Strategy

To solve this problem efficiently, we can use a dictionary to keep track of the count of each number as we iterate through the array. For each number, the count of good pairs for that number can be calculated using the number of times it has appeared so far. Here’s how:

  1. Initialize a dictionary to store the counts of elements seen so far.
  2. Iterate through the array:
    • For each element nums[i], check if it has been seen before.
    • If yes, add the current count of that element to the total number of good pairs.
    • Increment the count of the current element in the dictionary.
  3. Return the total number of good pairs after iterating through the array.

This approach ensures that we only pass through the array once, resulting in efficient time complexity.

Code

from collections import defaultdict

def numIdenticalPairs(nums):
    count = defaultdict(int)
    good_pairs = 0
    
    for num in nums:
        if num in count:
            good_pairs += count[num]
        count[num] += 1
    
    return good_pairs

# Example Usage
nums = [1,2,3,1,1,3]
print(numIdenticalPairs(nums))  # Output: 4

Time Complexity

This ensures an optimal solution for the given problem.

Try our interview co-pilot at AlgoAdvance.com