# 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).