## Friday, July 17, 2020

### Problem Statement

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.

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`

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

Array is the most basic data structures and common solutions inclue
• Nested for loops O(N^2)
• Sort O(NlgN)
• Use extra space O(N)
This applies to this problem perfectly. The O(N^2) brute force solution is naive. We can also use a Map data structure (key is the number, value is the occurrence count) thus O(N). We can also sort the array and use this simple formula (also leetcode's hint) to calculate the good number pair.
Good pairs = N * (N-1) / 2 where N is how many duplicate numbers, this is from combination C(n^2), from n elements pick two

### Solutions

#### Use Map

Time Complexity: O(N), N is the array size
Space Complexity: O(N) since we use extra Map

#### Sort

Time Complexity: O(NlgN), N is the array size since we sort
Space Complexity: O(1) no extra space is used

• None