Number of Good Pairs

2021-01-05

python algorithms_and_data_structures

Photo by Ben Allan

This post is part of the Algorithms Problem Solving series.

Problem description

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.

Examples

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) 0-indexed.

Example 2:

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

Example 3:

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

Solutions

The first solution that come to my mind, and maybe to yours too, is the idea to iterate through the list and compare each element in the list. In the comparison, we verify if the items are equal. If it is, just sum to the counter. And finally return the counter.

It's a brute force solution and the time complexity is O(n^2) and O(1) for the space complexity. But we can do better.

The second idea that came to my mind was to count each number in the list, do the permutation of each one, and return the sum of all these permutations. The code would look like this:

def factorial(n):
    if n <= 1: return 1
    return factorial(n - 1) * n

def permutation(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def number_of_good_pairs(nums):
    nums_counter = {}

    for num in nums:
        if num in nums_counter:
            nums_counter[num] += 1
        else:
            nums_counter[num] = 1

    counter = 0

    for num, num_counter in nums_counter.items():
        if num_counter > 1:
            counter += permutation(num_counter, 2)

    return counter

We calculate the permutation by using the formula n! / (n - r)! * r!, where n is the number of all numbers in the list and r is the positions we can combine these numbers.

To do the factorial, I created my own function, but we could also use the factorial function from the math module:

from math import factorial

def permutation(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

This is a O(n) solution in terms of time complexity. But now we are using a dictionary to compute the count for each number in the list, so the space complexity is O(n).

Another solution is to simplify the permutation, by just sum the occurrences of numbers to the counter like this:

def number_of_good_pairs(nums):
    nums_counter = {}
    counter = 0

    for num in nums:
        if num in nums_counter:
            counter += nums_counter[num]
            nums_counter[num] += 1
        else:
            nums_counter[num] = 1

    return counter

In this case, we could also use the Counter data structure to count using a dictionary for us:

from collections import Counter

def number_of_good_pairs(nums):
    nums_counter = Counter()
    counter = 0

    for num in nums:
        counter += nums_counter[num]
        nums_counter[num] += 1

    return counter

That way, we remove the need to verify if the nums_counter dictionary (or in this case, the Counter) already has the number inside it.

The time and space complexities are still both O(n).

Resources

Have fun, keep learning, and always keep coding!

My Twitter and Github