Leetcode – Number of Good Pairs Solution

Spread the love

The “Number of Good Pairs” problem on Leetcode is a classic introductory problem for those interested in array manipulation and combinatorial mathematics. Despite its apparent simplicity, the problem offers multiple angles to tackle it and can lead you into explorations of different techniques and time complexities. This article aims to provide an in-depth guide to understand the problem, explore various methods to solve it, analyze their efficiencies.

Problem Statement

The problem asks you to find the number of “good pairs” in an array of integers, nums. A pair (i, j) is called “good” if nums[i] == nums[j] and i < j.

Example

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

Brute-Force Approach: Nested Loops

The most straightforward approach is to use nested loops to compare each pair of elements in the array.

Python Code:

def numIdenticalPairs(nums):
    count = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                count += 1
    return count

# Test the function
print(numIdenticalPairs([1, 2, 3, 1, 1, 3]))  # Output should be 4

Time Complexity

The time complexity of this approach is O(n^2) because we use nested loops to compare the elements.

Space Complexity

The space complexity is O(1) since we only use a constant amount of extra space for the variable count.

Optimized Approach: Using Hash Map

You can solve this problem more efficiently by using a hash map (dictionary in Python) to keep track of the occurrences of each number in the array.

Python Code:

def numIdenticalPairs(nums):
    count = 0
    num_dict = {}
    for num in nums:
        if num in num_dict:
            count += num_dict[num]
            num_dict[num] += 1
        else:
            num_dict[num] = 1
    return count

# Test the function
print(numIdenticalPairs([1, 2, 3, 1, 1, 3]))  # Output should be 4

Time Complexity

The time complexity of this approach is O(n) because we traverse the array once, performing constant-time operations for each element.

Space Complexity

The space complexity is O(n) in the worst case when all elements are unique, and we need to store each of them in the dictionary.

Mathematical Approach: Using Combinatorics

You can leverage combinatorial mathematics to solve this problem. Specifically, if a number appears n times in the array, then the number of good pairs for that number would be

Python Code:

from collections import Counter

def numIdenticalPairs(nums):
    count = 0
    num_counts = Counter(nums)
    for num in num_counts.values():
        count += num * (num - 1) // 2
    return count

# Test the function
print(numIdenticalPairs([1, 2, 3, 1, 1, 3]))  # Output should be 4

Time Complexity

The time complexity is O(n) because the Counter class processes each element once.

Space Complexity

The space complexity is O(n) because we store the count of each unique number in a dictionary.

Conclusion

The “Number of Good Pairs” problem serves as an excellent stepping stone into the world of array manipulation and combinatorial mathematics. We explored a brute-force approach and two optimized methods that utilize a hash map and combinatorial mathematics. The problem provides a good playground to understand the trade-offs between time and space complexity and how to optimize algorithms for better performance. It also showcases how mathematical concepts can be applied to programming challenges.

Leave a Reply