# Number of Good Pairs
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-good-pairs)
Canonical: https://scaleengineer.com/dsa/problems/number-of-good-pairs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute Force using Nested Loops
This approach uses two nested loops to iterate through all possible pairs of indices `(i, j)` in the array. It checks if the elements at these indices are equal and if `i < j`. If both conditions are met, a counter is incremented.
**Time:** O(n^2), where n is the number of elements in the `nums` array. This is because for each element, we iterate through the rest of the array, leading to a quadratic number of comparisons. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Simple to understand and implement.; Requires no extra memory, making it space-efficient.
**Cons:** Inefficient for large arrays due to its quadratic time complexity.
### Explanation
The simplest way to solve the problem is to check every possible pair of indices `(i, j)` and see if they form a good pair. We can use a nested loop structure. The outer loop iterates from `i = 0` to `n-1`, and the inner loop iterates from `j = i + 1` to `n-1`. This structure naturally ensures that `i < j`. Inside the inner loop, we compare `nums[i]` and `nums[j]`. If they are equal, we've found a good pair and we increment our total count. After checking all pairs, the final count is the answer.

```java
class Solution {
    public int numIdenticalPairs(int[] nums) {
        int goodPairsCount = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    goodPairsCount++;
                }
            }
        }
        return goodPairsCount;
    }
}
```
### Algorithm
- Initialize a counter `goodPairsCount` to 0.
- Get the length of the array, `n`.
- Loop with an index `i` from `0` to `n-2`.
- Inside this loop, start another loop with an index `j` from `i+1` to `n-1`.
- Check if `nums[i]` is equal to `nums[j]`.
- If they are equal, increment `goodPairsCount`.
- After the loops complete, return `goodPairsCount`.

## Counting Frequencies in Two Passes
A more efficient approach involves counting the frequency of each number in the array first. If a number appears `k` times, it can form `k * (k - 1) / 2` pairs. We can sum these values for all numbers to get the total count of good pairs.
**Time:** O(n), where n is the number of elements. We perform one pass to build the frequency map and another pass over the unique elements (at most 101 in this case). This is a significant improvement over the brute-force approach. · **Space:** O(1), given the problem constraints (`1 <= nums[i] <= 100`), we can use a fixed-size array of 101. If the constraints were not fixed, it would be O(k) where k is the number of unique elements.
**Pros:** Significantly faster with O(n) time complexity.; The logic is based on a common combinatorial pattern.
**Cons:** Requires extra space to store the frequencies.
### Explanation
This method optimizes the counting process by first aggregating the data. Instead of comparing each pair, we count how many times each number appears in the array. We can use a Hash Map or, given the constraints `1 <= nums[i] <= 100`, a simple array of size 101 to store the frequency of each number. We iterate through the input array once to build this frequency map. After counting, we iterate through the frequencies. For any number that appears `k` times (where `k > 1`), the number of good pairs it can form is given by the combination formula 'k choose 2', which is `k * (k - 1) / 2`. By summing up these pair counts for every number, we get the total number of good pairs in the entire array.

```java
class Solution {
    public int numIdenticalPairs(int[] nums) {
        int[] counts = new int[101];
        for (int num : nums) {
            counts[num]++;
        }

        int goodPairsCount = 0;
        for (int count : counts) {
            if (count > 1) {
                goodPairsCount += (count * (count - 1)) / 2;
            }
        }
        return goodPairsCount;
    }
}
```
### Algorithm
- Create a frequency array `counts` of size 101 (based on constraints) and initialize it to zeros.
- Iterate through the `nums` array and populate the frequency array. For each `num`, increment `counts[num]`.
- Initialize a counter `goodPairsCount` to 0.
- Iterate through the `counts` array.
- For each frequency `k`, calculate the number of pairs it can form using the formula `(k * (k - 1)) / 2` and add it to `goodPairsCount`.
- Return `goodPairsCount`.

## Optimized Single-Pass Counting
This is the most efficient approach. It combines counting frequencies and calculating pairs into a single pass through the array. As we iterate, we use a frequency array to keep track of the counts of numbers seen so far. For each number, we add its current count to our total before incrementing its count in the map.
**Time:** O(n), as we iterate through the array only once. · **Space:** O(1), due to the problem's constraints on the values in `nums`, allowing a fixed-size array. Without these constraints, it would be O(k) for k unique elements.
**Pros:** Most efficient approach with a single pass over the data.; Combines counting and calculation, which can be slightly faster in practice than the two-pass method.
**Cons:** Requires extra space, similar to the two-pass approach.
### Explanation
This approach refines the frequency counting method by calculating the good pairs on the fly in a single pass. We initialize a counter for good pairs and a frequency array. We iterate through the `nums` array. For each element `num`, we first look up its current frequency in our array. Let's say we have seen `num` `k` times already. This means the current `num` can form `k` new good pairs with the ones we've already encountered. So, we add `k` to our total `goodPairsCount`. Then, we update the array by incrementing the frequency of `num` by 1 to account for the current element. This way, we build the counts and sum the pairs simultaneously.

```java
class Solution {
    public int numIdenticalPairs(int[] nums) {
        int goodPairsCount = 0;
        int[] counts = new int[101]; // Constraints: 1 <= nums[i] <= 100
        for (int num : nums) {
            // The current number `num` can form a pair with all previous occurrences.
            // The number of previous occurrences is `counts[num]`.
            goodPairsCount += counts[num];
            // Increment the count for the current number for subsequent elements.
            counts[num]++;
        }
        return goodPairsCount;
    }
}
```
### Algorithm
- Initialize `goodPairsCount` to 0.
- Initialize a frequency array `counts` of size 101 with all zeros.
- Iterate through each `num` in the `nums` array.
- For the current `num`, the number of pairs it can form with previous identical numbers is `counts[num]`. Add this value to `goodPairsCount`.
- Increment the count for the current number: `counts[num]++`.
- After the loop, return `goodPairsCount`.

# Solutions
### Java

```java
class Solution {
public
  int numIdenticalPairs(int[] nums) {
    int ans = 0;
    int[] cnt = new int[101];
    for (int x : nums) {
      ans += cnt[x]++;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var numIdenticalPairs =
  function (nums) {
    const cnt = Array(101).fill(0);
    let ans = 0;
    for (const x of nums) {
      ans += cnt[x]++;
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: int numIdenticalPairs ( vector < int >& nums ) { int ans = 0 ; int cnt [ 101 ]{}; for ( int & x : nums ) { ans += cnt [ x ] ++ ; } return ans ; } };
```

### Python

```python
class Solution : def numIdenticalPairs ( self , nums : List [ int ]) -> int : ans = 0 cnt = Counter () for x in nums : ans += cnt [ x ] cnt [ x ] += 1 return ans
```