Number of Good Pairs - Leetcode 1512 - Python

0:00 - Read the problem / Brute force
1:50 - Drawing Explanation 1
5:51 - Coding Explanation 1
7:19 - Drawing Explanation 2
10:01 - Coding Explanation 2

leetcode 1512

#neetcode #leetcode #python

[kirillzlobin]

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

[sadiksikder]

It's actually the combination formula nCr

[picnicbros]

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

[divyeshbatra]

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 =

return sumresult

[priyamf]

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.

[two]

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

[werstef]

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?

[JammUtkarsh]

Greats It's my Day 29 streak question!

[kamalsinghbisht]

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
"