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
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
Have fun, keep learning, and always keep coding!