We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Good Pairs

Number: 1635

Difficulty: Easy

Paid? No

Companies: Amazon, Zoho, Google, Adobe, Apple, Uber, Bloomberg, Meta

Problem Description

Given an array of integers, determine the number of "good pairs". A pair (i, j) is considered good if nums[i] equals nums[j] and i < j.

Key Insights

  • Use counting to determine how many times each number appears.
  • For every occurrence of a number, the number of good pairs contributed by that occurrence is the count of that number seen so far.
  • A hash table is ideal for tracking frequencies quickly.
  • The pair counting can be done in one pass through the array.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input array. Space Complexity: O(n) in the worst case due to the frequency hash table.

Solution

We utilize a hash table (or dictionary) to map each number to its frequency of occurrence as we iterate through the list. Each time we encounter a number, we add its current frequency (which represents the number of times it has appeared before) to the overall count of good pairs. Then, we increment its frequency in the hash table. This method counts the pairs in a single pass, making the solution efficient in both time and space.

Code Solutions

# Python solution to count the number of good pairs in an array

def num_identical_pairs(nums):
    # Dictionary to store the frequency of each number
    frequency = {}
    count = 0
    # Iterate over each number in the list
    for num in nums:
        # If the number is already seen, add its current frequency to count
        if num in frequency:
            count += frequency[num]
            frequency[num] += 1  # Increment the frequency
        else:
            frequency[num] = 1  # Initialize frequency for new number
    return count

# Example usage:
nums = [1, 2, 3, 1, 1, 3]
print(num_identical_pairs(nums))  # Expected output: 4
← Back to All Questions