Pairs with given sum in an array (code/Algorithm)

Find pairs with the given sum in an array. Give the algorithm.

[@VinayK22]

This algorithms is only for distinct elements fails for duplicates in array

[@mdnayab5839]

correct

[@tintiniitk]

@@mdnayab5839 The fix for duplicates needs a small improvement to this. This is especially harder when there are duplicates both on the high and the low side at the same time. To handle duplicates, instead of just storing l, r indices, you also need to store something like the indices where l last changed (let's say lAnchor) and the index where r last changed (rAnchor), and keep incrementing l and r if they are same on moving forward. Now num += (l - lAnchor) * (rAnchor - r). Now reset lAnchor = ++l and rAnchor = --r . And repeat.

[@RahulYadav-nl1ek]

@@tintiniitk but it will increase the complexity we are already in nlogn after sorting if we use extra space we can do this in O(n) time and O(n) space with duplicates

[@bikramjitdas2621]

@@tintiniitk could you just trace an example with this approach

[@tintiniitk]

As has been pointed out by some, this doesn't handle duplicates at all. The fix for duplicates needs a small improvement to this. This is especially harder when there are duplicates both on the high and the low side at the same time. To handle duplicates, instead of just storing l, r indices, you also need to store something like the indices where l last changed (let's say lAnchor) and the index where r last changed (rAnchor), and keep incrementing l and r if they are same on moving forward. Now if array[l] + array[r] == sum, num += (l - lAnchor) * (rAnchor - r). After this, reset lAnchor = ++l ; rAnchor = --r . And repeat.

[@tintiniitk]

This approach is O(n.log n). A much better O(n) approach is using hashmaps. array -> hashmap . hashmap in c++ is unordered_map. int count = 0; for (auto kv: hashmap) { if (kv.first * 2 == sum) count += kv.second * (kv.second - 1) / 2; else if (kv.first < sum - kv.first) { count += hashmap[sum - kv.first]; } return count; }

[@ankan1994]

i am promoting ur channel among my friends and they all find ur videos very helpful

[@partapupreetham9518]

This algorithm fails for duplicate elements

[@prateektripathi100]

Awesome.....can't describe in words how amazing explanation it is

[@ankan1994]

very important and frequently asked array question...thanks for uploading sirji..a similar type of question which is faced by me in interview-let we have an given array of only (1) and (-1) as elements like arr[1,-1,-1,1,1,-1.....1] so we have to count the number of sub-arrays forming the sum 0.For eg- arr[1,-1,1,-1] here no of sub arrays is 4. i know how to do it, but still i want to get it from u bcoz u always bring the best and optimal solution.

[@Rajveer0400]

Best video ever for the array ...simple and easy concept cleared thank you so much ...

[@naturebc]

for i = 0; i< array.length; for j = i+1; j

[@dobbyunleashed]

This method does not work in case you have some numbers which are repeating multiple times in array.

[@mdnayab5839]

@Fatima faz i did not got your point. can you plz share a code snippet?

[@TheMohit987]

Right

[@TheMohit987]

@@mdnayab5839 This is not a full-proof solution. ❌❌❌ Like if input is: [2 -6 2 5 2 ] then right output should be [2 2], [2 2], [2 2] where as your code will return only two pairs.

[@milindjain544]

Awesome lecture too clear and crisp

[@dineshkathania2228]

No need of sorting we can write in python in simple logic and it will cover all pair like duplicate numbers also:- def printPairs(arr, n, sum): for i in range(0, n ): for j in range(i + 1, n ): if (arr[i] + arr[j] == sum): print(arr[i],arr[j])

[@preetsingh2133]

It is failing in 2 2 2 2 2 (sum is 4) case

[@tapanjeetroy8266]

Thanks for uploading it.. You are doing a great job.. Please upload more videos of competitive programming.. We really need it

[@Ankit13555]

also plzz discuss the O(n) as per to me...worst case will be O(nlogn)-->sorting +n for checking all nos ...is it correct?

[@kabooby0]

You can do this in O(n) time with a hashmap

[@devanshprakash8354]

Is this two sum problem?

[@sarahdaniel6862]

This logic exceeds time limit on geeks for geeks.

[@em_ashutosh]

sort krtai hi game over

[@vikassrivastava6459]

Hi Vivekanand - could you please upload a complete lecture on bit manipulation with some of the examples which will help in understanding the concept Thanks in advance

[@rajaindirajith1534]

In the else case you can do l++; and r--; not or. because if the sum produce by the two number will not produce the result with any other combination

[@abhishekat8032]

what if that array has duplicate items

[@netturikowshikbasha4811]

1 2 3 4 5 6 the output of code is 2 but actullay 3

[@rajeshd7389]

Hi.... nice explanation !!!! But this algorithm has time complexity O(nlogn) or O(n2) depending upon sorting technique used .... Can you extend this approach to hashing which has time complexity O(n).

[@Nognamogo]

I'm pretty sure the sorting algorithm is ignored here. Sorting is only worth it if you'll be running multiple algorithms on the same data. Without the sorting it's O(n) which is what the video meant.

[@mcaddit6802]

awesome approach sir

[@snehasisbarat2457]

How to solve this problem if the array is unsorted and required time complexity is O(N)?

[@bhaskarnaik5842]

I need explanation of this topic given a sorted and rotated array, find if there is a pair with a given sum

[@akhileshswaroopxisrnnadbt3669]

How to solve when there are duplicate elements in array or all elements in array are same?

[@45_ritiksharma32]

Could you please explain the logic behind this code

[@swethag1146]

Thanks for this approach. Satisfies duplicate as well. Java code below... int[] num = {1,2,3,4,5,6,7,8}; Arrays.sort(num); int sum = 6; int i = 0; int j = num.length - 1; boolean found = false; while(i sum) j--; else if(num[i] + num[j] < sum) i++; else if(num[i] + num[j] == sum){ System.out.println(num[i] +","+ num[j]); i++; j--; found = true; } } if(!found) System.out.println("pair not found");

[@sayantaniguha8519]

what kind of a code is this / not working

[@akhileshswaroopxisrnnadbt3669]

@Vivekanand Khyade - Algorithm Every Day :How to solve when there are duplicate elements in array or all elements in array are same?

[@ihowaonaro4511]

This is great but it doesnt consider if the array has duplicate elements. e.g if there were two 10's you would miss the sum

[@Prophetsarkar]

sir in the if(arr[l]+arr[r]>GS) why you put (l++) can we put (r--) there?

[@sagar1u]

sir this video satisfies the condition of pairs ,but if we want combination of 3 or 4(suppose a[4,1,5,6,9,0,-1,20] and sum require is 31 then it has to be return [5,6,20]) elemnets from the array then what is the code or logic

[@Vishal-nc8ju]

best channel

[@RajaSekhar-te5nz]

Do the program on substracting adjacent numbers in array and finally display sum of all

[@shilpika9942]

sir when you find a pair and you print it then why we have to either do l++ or r-- why not both ? can u please explain?

[@vikramsingla3217]

"l++ or r--" Why to do only one of these. If we do both l++ and r--, does it make any difference? Doing both seems more correct approach to me.

[@fuadhasan0362]

thank you sir!! love and respect from bangladesh

[@amolshelke9651]

can you please send here link of the code ..github ??

[@mohammadwahiduzzamankhan4397]

Your explanation is amazing.

[@sayankundu485]

Suppose it says given sum = 3 ... Then how will this algorithm work

[@devanshprakash8354]

Is this the two sum problem?

[@seraj_valley]

no need of sorting use the concpt of hashing

[@gamingroom6421]

This method will work for only two element pairs

[@AllTypeShorts..]

please explain the logic behind this code sir................

[@tanveer.shaikh]

Your solution is O(nlog n)

[@surajrohankar1028]

In this example 1+2+8=11, 1+2+3+5=11 and so on, then how can we make it dynamic?

[@vamsisaikrishnapaturu2261]

only pairs (2 numbers only)

[@cricbolly3252]

Great sir

[@rahulkolte1581]

but it is giving only two elements pairs (1,2,8) this also sum is 11

[@avinashch4811]

Gs = 11 I want to get [1,3,7] as output how to write code for that ?

[@alokcom]

Thats triplet in array in array question.

[@ankitchawla8487]

This algorithm dosen't work for duplicate elements.

[@amolshelke9651]

what if instead of finding pair of elements .. i want any number of elements whose sum is equal to given number ??

[@varshapatil5263]

I also want solution for same problem If you have plz share with me

[@shiva_gaming8122]

wha if all the elements are equal

[@suneelsai9981]

6+4+1 =11 is also a pair right?

[@lesnar229]

Why need to sort arr

[@TheMohit987]

This is not a full-proof solution. ❌❌❌ Like if input is: [2 -6 2 5 2 ] then right output should be [2 2], [2 2], [2 2] where as your code will return only two pairs.

[@meenakshirana7664]

Video explanation is good. But this approach of finding the count doesn't work, in case if array consists of duplicates.

[@harderharder6713]

the algorithm that he has mentioned will work in case of duplicates because he is not incrementing R and decrementing L simultaneously when a pair is found ...You are talking about the case when you increase and decrease them in a single step when a pair is found..

[@sukhangadsingh742]

fails for {1,1,1,1}

[@saikatdutta1991]

how ?

[@jermainegoss705]

Can you please do quadruple sum to target? pretty please lol

[@pranaywelekar4060]

can u send the correct code once

[@himanshubhatt6240]

Thanks 😊

[@mowglishihtzutoy5197]

Lot of love

[@yashchandraverma3131]

Thanks

[@prashantverma3347]

thank you

[@ta3113ta]

Thank you sir.

[@kirankumarmv2771]

This algo works for duplicates aswell.. only thing is we have to have sorted array in first place.

[@45_ritiksharma32]

Please post more vidios

[@kirankumarmv2771]

we have to do both l++ & r--, as and when we found sum.

[@aravindg6129]

Bro whats the complexity

[@jamesqiu6715]

What??? why need to sort the array first ? Is this the "2 sum" problem ?

[@dileepalla6769]

thanks i learn

[@orz5516]

thank you from israel. u are great.

[@insaniyat_1512]

respect

[@vincenr8822]

HELLO FRIENDS :)

[@vivekanandkhyade]

Thanks Vinster..!

[@arjunnatukula7128]

@@vivekanandkhyade codes plz

[@backtobasics6865]

not a good solution

[@Fhhchchcddd]

हिंदी में बोल ले भाई

[@neerajmahapatra5239]

At least explain the logic behind your code just explaining code...😞

[@DeepakSingh-mw9bf]

Waste of time🙄