Number of Good Pairs - Leetcode 1512 - Python

[@kirillzlobin7135]

This man should be the first one who solved all leetcode problems on KZbin

[@nur_6ek]

bro you are legend 😅

[@priyam86f]

A fun story. When I first looked at the problem, I thought of searching for a pattern, let's say. if the array had [1,1] number of pairs = 1. similarly, if nums = [1,1,1], pairs = 3. now, if nums=[1,1,1,1] pairs = 6. finally, if nums = [1,1,1,1,1] pairs = 10. so by now I was sure, the "number of pairs" had a pattern while increasing, at first it was 1,then 3 then 6 and then 10. which means, it first incremented by just 2 [3], then by 3 [6] , then by 4[10]. I just couldn't code the solution up,but i guess i was on the same page! Intuitions are just crazy,cheers neet.

[@picnicbros]

The pair-counting is a sub problem of LeetCode 2421- Number of Good Paths

[@sadiksikder7014]

It's actually the combination formula nCr

[@NikolayMishin]

very good explanation, thank you

[@divyeshbatra6719]

class Solution: def numIdenticalPairs(self, nums: List[int]) -> int: resultdict={} sumresult=0 for index, x in enumerate(nums): if x in resultdict: resultdict[x].append(index) else: resultdict[x] = [index] for key,value in resultdict.items(): if len(value)>1: sumresult = sumresult+sum(range(len(value))) return sumresult

[@JammUtkarsh]

Greats It's my Day 29 streak question!

[@two697]

Hey, could you start posting more videos about hard or difficult medium problems if you get the time? I think questions like leetcode 587 and 834 are really interesting

[@vour6654]

he is doing the daily questions.

[@krateskim4169]

Awesome recess

[@werstef8681]

hmm, help me if I am wrong but isnt that a combinations of n taken 2 and then divided by 2? mathematically it seems correct but 4 cases give me incorrect. can you help me?

[@mokoboko2482]

legendary

[@shreyaschaudhary-r6d]

the second solution is better imo!

[@kamalsinghbisht1964]

Time Complexity - O(N) Space Complexity - O(1) Solution : "class Solution: def numIdenticalPairs(self, nums: List[int]) -> int: n = len(nums) good_pair = 0 nums.sort() i ,j = 0, 1 while j < n : if nums[i] != nums[j] : x = j - i - 1 good_pair += x*(x+1)//2 i = j j = j+1 x = j - i - 1 good_pair += x*(x+1)//2 return good_pair "

[@yfjsdgzjdnfn]

Sorting takes O(n log n) even if we use sort()

[@akhilchauhan9417]

bruh