@@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.
@@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
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.
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; }
@@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.
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).
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.
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
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
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.
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.
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..
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])
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;
This algorithms is only for distinct elements fails for duplicates in array
correct
@@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.
@@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
@@tintiniitk could you just trace an example with this approach
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.
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;
}
i am promoting ur channel among my friends and they all find ur videos very helpful
This method does not work in case you have some numbers which are repeating multiple times in array.
@Fatima faz i did not got your point. can you plz share a code snippet?
Right
@@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.
This algorithm fails for duplicate elements
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?
Awesome.....can't describe in words how amazing explanation it is
Awesome lecture too clear and crisp
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).
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.
Best video ever for the array ...simple and easy concept cleared thank you so much ...
It is failing in
2 2 2 2 2 (sum is 4) case
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
@Vivekanand Khyade - Algorithm Every Day :How to solve when there are duplicate elements in array or all elements in array are same?
I need explanation of this topic given a sorted and rotated array, find if there is a pair with a given sum
Could you please explain the logic behind this code
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
"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.
You can do this in O(n) time with a hashmap
Is this two sum problem?
How to solve when there are duplicate elements in array or all elements in array are same?
Thanks for uploading it.. You are doing a great job.. Please upload more videos of competitive programming.. We really need it
How to solve this problem if the array is unsorted and required time complexity is O(N)?
awesome approach sir
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.
sir in the if(arr[l]+arr[r]>GS) why you put (l++) can we put (r--) there?
This logic exceeds time limit on geeks for geeks.
sort krtai hi game over
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?
Suppose it says given sum = 3 ... Then how will this algorithm work
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
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
what if that array has duplicate items
6+4+1 =11 is also a pair right?
Do the program on substracting adjacent numbers in array and finally display sum of all
In this example 1+2+8=11, 1+2+3+5=11 and so on, then how can we make it dynamic?
only pairs (2 numbers only)
for i = 0; i< array.length;
for j = i+1; j
but it is giving only two elements pairs (1,2,8) this also sum is 11
Is this the two sum problem?
Can you please do quadruple sum to target? pretty please lol
what if instead of finding pair of elements .. i want any number of elements whose sum is equal to given number ??
I also want solution for same problem
If you have plz share with me
please explain the logic behind this code sir................
best channel
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.
1 2 3 4 5 6
the output of code is 2 but actullay 3
wha if all the elements are equal
This algorithm dosen't work for duplicate elements.
Video explanation is good. But this approach of finding the count doesn't work, in case if array consists of duplicates.
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..
Great sir
no need of sorting use the concpt of hashing
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])
fails for {1,1,1,1}
how ?
Gs = 11
I want to get [1,3,7] as output how to write code for that ?
Thats triplet in array in array question.
can you please send here link of the code ..github ??
Your explanation is amazing.
This method will work for only two element pairs
Your solution is O(nlog n)
Why need to sort arr
thank you sir!! love and respect from bangladesh
Thanks 😊
can u send the correct code once
Thanks
What??? why need to sort the array first ? Is this the "2 sum" problem ?
Lot of love
This algo works for duplicates aswell.. only thing is we have to have sorted array in first place.
Bro whats the complexity
Thank you sir.
thank you
Please post more vidios
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");
what kind of a code is this / not working
thanks i learn
respect
we have to do both l++ & r--, as and when we found sum.
HELLO FRIENDS :)
Thanks Vinster..!
@@vivekanandkhyade codes plz
At least explain the logic behind your code just explaining code...😞
thank you from israel. u are great.
not a good solution
हिंदी में बोल ले भाई
Waste of time🙄