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.
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
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
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?
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
This man should be the first one who solved all leetcode problems on RUclips
bro you are legend 😅
The pair-counting is a sub problem of LeetCode 2421- Number of Good Paths
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.
very good explanation, thank you
It's actually the combination formula nCr
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
he is doing the daily questions.
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
Greats It's my Day 29 streak question!
Awesome recess
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?
legendary
the second solution is better imo!
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
"
Sorting takes O(n log n) even if we use sort()
bruh