Number of Good Pairs | 3 Approaches | META | Leetcode - 1512

This is the 6th Video on our HashMap/Set Playlist.
In this video we will try to solve an easy but good Problem - Number of Good Pairs (Leetcode-1512).

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Remove Colored Pieces if Both Neighbors are the Same Color
Company Tags : META

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[codestorywithMIK]

Kindly ignore nCr relation here at 5:01 . If a number appears n times, then we will have n * (n – 1) / 2 good pairs . See the logic from example {1, 1, 1, 1}.
Let me explain here the depth of n*(n-1)/2

For example a number appears n = 4 times - {1, 1, 1, 1}
For 1st 1, possible pairs = 3
For 2nd 1, possible pairs = 2
For 3rd 1, possible pairs = 1
So total = 3 + 2 + 1

For example a number appears n = 5 times - {2, 2, 2, 2, 2}
For 1st 2, possible pairs = 4
For 2nd 2, possible pairs = 3
For 3rd 2, possible pairs = 2
For 4th 2, possible pairs = 1
So total = 4 + 3 + 2 + 1

So generalising for n occurrences,
total = (n-1) + (n-2) + + 1
i.e. Sum of 1st (n-1) natural numbers = (n-1) * (n-1+1)/2 = ((n-1) * n / 2 = n*(n-1)/2

[manaskhare]

Thanks for the explanation!, Here is my approach with N complexity with constant space using 2 pointer,
class Solution {
public:
int nums) {
int n = nums.size();
int i= 0, j=i+1, cnt = 0;

while(i!=n-1) {
if(nums[i] == nums[j]) cnt ++;
j++;

if(j==n) {
i++;
j = i+1;
}
}

return cnt;
}
};

[Momentsofmagic]

I knew I will learn something new even from an easy Qn when I watch your video. Thank you Legend

[DurgaShiva]

Last approach to travers ONLY ONCE, and compute the result using map is epic... hats off

[wearevacationuncoverers]

Loved the simplicity of the explanation. Thanks a lot.

[drbullah]

Bhaiya, I solved this problem on my own. First I came up with brute force approach of n^2 and then came to ncr solution but it was giving me buffer overflow as i was calculating factorials. I reduced the calculations by using math and came up with this. Thank you for teaching me how to solve problems from the ground up.
int nc2 (int n){
if(n <= 0)
return 0;
return (n - 1)*(n)/(2);
}
int nums) {
int n = nums.size();
int ans = 0, size;
unordered_map<int, int> umap;
for(int i = 0 ; i < n ; i++){
umap[nums[i]]++;
size = umap[nums[i]];
ans += (nc2(size) - nc2(size - 1));
}
return ans;
}
};

[ayushsaxena]

Sir Please cover Dp and graph questions of cses problemset . It has some really nice questions . Your explanations resonates with students quite well.

[ugcwithaddi]

I learn something from every video of yours

[abhishekverma]

iska follow up aur bhi acha question h..
same concept pe h.
leetcode 2001: Pair of Interchangeable Rectangles..

aur bhya apki 3rd approach kafi intuitive lagi mreko..

[souravjoshi]

Loved the 3rd approach bro. Thanks a lot

[nadeking]

Thank you for great explanation (as always), just can you clear a part how you came up with the relation n(n-1)/2

[vasugaur]

Third approach ki space complexity is O(N) right?

[kamranwarsib]

Hey mik i have a question that i have given oa's for internship in Microsoft, linkedin etc but haven't seen questions regarding trees and linked list . So should i prepare them for my oa's or should i just revise them for my tech interview