Number of Good Pairs (LeetCode 1512) | Full solution with visuals and examples | Study Algorithms

Given an array, we need to find the number of good pairs that can be formed with the elements. A pair is said to be good if the elements are same and the left index is smaller than the right index. Watch the video to see a visual example of how the pairs are determined. The video also explores a progressive way to arrive at an optimal solution along with a dry-run of the code. Simple maths can be wonderful at times.

Chapters:
00:00 - Intro
01:11 - Problem statement and description
04:54 - Brute Force approach to find good pairs
07:09 - Efficient method to find good pairs
10:52 - Dry-run of Code
12:53 - Final Thoughts

📚 Links to topics I talk about in the video:

📖 Reference Books:

🎥 My Recording Gear:

💻 Get Social 💻

#leetcode #programming #interview

[TiagoDiass]

man, that's thinking out of the box, great! I solved the problem with the brute force approach but I did realize "bro, this looks bad, its a O(n²) algorithm, thats no good for time" but I couldnt think of a way to solve it with O(n), thank you!

[devanshsrivastava]

thank u for the explanation for how to think the optimise solution

[sajiyasalat]

i dont understand why there is so much less views on this you explain in such a perfect manner... i was not able to understand que but i know its optimised way..to solve

[Webeverse.]

Hii bruh, could you give me some efficient tips to solve problems using data structures and how can i choose efficient algorithm for solving particular probs?

[Dadycalling]

Going ahead with your optimised solution, I've removed that nC2 calculation part and I'm adding count[num]++ to totalCount in the first for loop only.


class Solution {
public int numIdenticalPairs(int[] nums) {

int[] count = new int[101];
int totalCount = 0;
for(int num : nums) {
totalCount+=count[num]++; //using the fact that count[num]++ is updated after assignment
}
return totalCount;
}

[bindhumadavalibindhu]

tq sir i understood very will with u r explation

[SubhajitDas-mtsn]

//cpp
class NumberOfGoodPairs {
public:
int nums) {
// Calculate the frequency of each number
vector<int> count(102, 0);

for (int num : nums) {
count[num]++;
}

int totalCount = 0;

// Calculate total number of pairs possible
for (int i : count) {
totalCount += (i * (i - 1)) / 2;
}

return totalCount;
}
};

[heyOrca]

Thank you Nikhil Lohia✨🫂

14th, Sept 2024 -11:53

[muthukumara]

will it work for all the cases?array size is 102, what if any number comes like 110 ?

[anshulkupadhyay]

How will the space complexity be 0(1) while you are creating addition freq array of size biggest number in the original array?

[crosswalker]

I tried to find a pattern in which the count is appearing, and this is how I did my code. I knew about the permutation&combination method, but I couldn't remember the formula.


int nums) {
unordered_map<int, int>mp;
int n = nums.size();
int count =0;
for(int i=0;i<n;i++){
mp[nums[i]]++;
if (mp[nums[i]]>1){
count = count + mp[nums[i]] -1;
}
}
return count;
}

[mahimatolani]

If the limitation is size of input array is 100 why we took 102 size of count array?

[piyushpatidar]

Can you Explain AND xor OR problem on hackerrank in stack data structures part

[shubhamsaxena]

Can someone confirm why the size of count array has been taken as 102 ?

[nx]

A quick question how is efficient approach has O(n) time complexity?

[me-ooh-no]

Can anyone expalin why time complexicity is O(n) instead of O(2n) we are using 2 for loops ?

[solar]

How is it order of (N) since we have to populate the hashmap?

[gokulakannan]

i*(i-1)/2 this formula, i can't understand.... how it is same with combination formula

[arslanmuhammad]

Love You Believe Me You are Doing Great. Please Help me to Understand AVL Tree. I am unable to understand how to maintain the height of it. I spend 30 days to do that but still unable to understand that.

[the_story_mode]

A more optimized logic could be

// Coding in Javascript

function numIdenticalPairs(nums) {

let count = 0, freq = {}

for(let i=0;i<nums.length;i++){
let num = nums[i]

if(freq[num]!==undefined){
count = count + freq[num]
freq[num] += 1
}else{
freq[num] = 1
}
}

return count


}