Problem Statement

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.

Constraints:

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 100

Explanation

Here, we need to find the number of good pairs in an array

Good Pairs: Pair of the same numbers present in the array

In Example 1, nums = [1,2,3,1,1,3]
There are 4 good pairs: (0,3), (0,4), (3,4), (2,5)

1 present on 0 index form good pairs with 1 at 3 and 4 index
1 at 3 and 4 index also forms a good pair
3 at 2 and 5 index forms a good pair

Solution

• Brute Force Approach

  We can traverse the whole array for each element and will do count++ whenever the condition nums[i] == nums[j] gets fulfilled

  - count -> variable to count the total number of good pairs
  - i -> to traverse the outer loop from 0 to n-2
  - j -> to traverse the inner loop from i+1 to n-1

Consider nums = [1,2,1,1]
- i will traverse the loop from 0 to 2
- suppose i = 0, j will traverse the loop from 1 to 3. When j=2, nums[i] == nums[j] gets fulfilled so count will be incremented by 1 means we have a good pair
The same thing will happen in the rest of the iterations

[ Here i traverse up to n-2 not n-1 because if i=n-1 means 3 in the above case then j=4 which will make out of bounds exception occur ]

public int numIdenticalPairs1(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                if (i < j && nums[i] == nums[j])
                    count++;
            }
        }
        return count;
    }

when,
i=0 then iterations -> 3
I=1, iterations -> 2
i=2 iterations ->1
Total Iterations = 3 + 2 + 1
In general, n-1 + n-2 + ... + 1 = n(n-1) / 2
on solving n(n-1)/2, Time Complexity = O(n^2)

• Optimized Solution

Consider nums = [2,3,2,2]
↓
0 1 2 3 ->indices
2 3 2 2 -> nums

- Here pointer(↓) is on 0 index so nums[0] = 2, you can see that there is no element before it so there is no good pair for now

__↓
0 1 2 3 ->indices
2 3 2 2 -> nums
- Now ↓ is on 1 index so nums[1] = 3, there is 2 before 3 but they can't form a good pair

____↓
0 1 2 3 ->indices
2 3 2 2 -> nums
- Now ↓ is on 2 index so nums[2] = 2, there is one 2 before it so it can form 1 good pair

______↓
0 1 2 3 ->indices
2 3 2 2 -> nums
- Now ↓ is on 3 index so nums[3] = 2, there are two 2's before it so it can form 1 good pair with each
Total Good Pairs = 3

From this you can observe that if the same number occurs before the current number then they will form a good pair. Like above 2 at index 3 will form 2 good pairs with the two 2's occurring before it

SO NOW HOW WE CAN CODE IT?

• Traverse the whole array

• calculate the occurrence of the current number before it

• sum the total good Pairs

public int numIdenticalPairs(int[] nums) {
        int pairs = 0; // to count good pairs
        int count[] = new int[101]; // to store the occurence of a number

        for (int i = 0; i < nums.length; ++i) {
            pairs = pairs + count[nums[i]];
            count[nums[i]]++;
        }

        return pairs;
    }

Logic to calculate the occurrence of a number

Consider an array arr=[1,3,2,1,1,2]
- to calculate the occurrence of 1, 2 and 3 we define an array count of size 4.
- we will treat element of arr as index in count
- when we encounter an element then we will increase 1 in that index in count array
means,
if we the element is 1 then we will increase 1 in count[1]
if element is 3 then we will increase 1 in count[3]

for arr,
0 1 2 3 ->index
0 3 1 1 -> count
[NOTE: count size is 4 because max element in arr is 3 so we need index value only up to 3. Any value greater than this will be the wastage of memory ]

In Above code, nums[i] is the element and count[nums[i]]++ means we are increasing its occurence in count by 1

Thanks for reading this blog, I Hope it helped you in understanding the question better.
If you want more solutions like this then subscribe to my newsletter, I am making a series of DSA-Days in which I will post one solution a day of leetcode question. The series will cover all types of questions like Easy/Medium/Hard and they will be topic-wise.