# Number of Good Pairs

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!