# Number of Good Pairs — Day 101(Python)

--

After a long hiatus, I decided to start writing again as a new year resolution. I wanted to start with something easy, hence choosing the following problem.

## 1512. Number of Good Pairs

Given an array of integers `nums`

, return *the number of *** good pairs**.

A pair `(i, j)`

is called *good* if `nums[i] == nums[j]`

and `i`

< `j`

.

**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

**Constraints:**

`1 <= nums.length <= 100`

`1 <= nums[i] <= 100`

This question is very similar to Two Sum. We have solved this problem before. You can find it here.

A brute force method will traverse through the list of numbers and check if the numbers match.

`class `**Solution**:

def **numIdenticalPairs**(self, nums: List[int]) -> int:

output = 0

for i in range(len(nums)):

for j in range(i+1, len(nums)):

if(nums[i] == nums[j]):

output += 1

return output

**Complexity**

**Time Complexity**

Since we have 2 for-loops here, hence time complexity is O(N²).

**Space Complexity**

We are not using any extra space, and hence the space complexity will be O(1).

An optimized method will traverse through the list once, but to save time we use a dictionary to store already traversed elements. The keys will be traversed elements and the values will be the number of times we have seen that number.

`class `**Solution**:

def **numIdenticalPairs**(self, nums: List[int]) -> int:

output = 0

dict_number = dict()

for n in nums:

if n in dict_number:

output += dict_number[n]

dict_number[n] += 1

else:

dict_number[n] = 1

return output

**Complexity**

**Time Complexity**

Since we have 1 for-loop here. Hence time complexity is O(N).

**Space Complexity**

We are not using any extra space and hence the space complexity will be O(N).