@@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.
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 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
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
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])
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..
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 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 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
Awesome.....can't describe in words how amazing explanation it is
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.
Awesome lecture too clear and crisp
This algorithm fails for duplicate elements
Best video ever for the array ...simple and easy concept cleared thank you so much ...
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?
How to solve this problem if the array is unsorted and required time complexity is O(N)?
It is failing in
2 2 2 2 2 (sum is 4) case
awesome approach sir
@Vivekanand Khyade - Algorithm Every Day :How to solve when there are duplicate elements in array or all elements in array are same?
Could you please explain the logic behind this code
You can do this in O(n) time with a hashmap
Is this two sum problem?
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.
I need explanation of this topic given a sorted and rotated array, find if there is a pair with a given sum
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
Is this the two sum problem?
This logic exceeds time limit on geeks for geeks.
sort krtai hi game over
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
sir in the if(arr[l]+arr[r]>GS) why you put (l++) can we put (r--) there?
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
6+4+1 =11 is also a pair right?
best channel
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
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
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)
"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.
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
wha if all the elements are equal
for i = 0; i< array.length;
for j = i+1; j
can you please send here link of the code ..github ??
Why need to sort arr
thank you sir!! love and respect from bangladesh
Great sir
Do the program on substracting adjacent numbers in array and finally display sum of all
can u send the correct code once
Gs = 11
I want to get [1,3,7] as output how to write code for that ?
Thats triplet in array in array question.
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
but it is giving only two elements pairs (1,2,8) this also sum is 11
Your explanation is amazing.
Can you please do quadruple sum to target? pretty please lol
Thanks 😊
please explain the logic behind this code sir................
Lot of love
fails for {1,1,1,1}
how ?
thank you
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])
Bro whats the complexity
1 2 3 4 5 6
the output of code is 2 but actullay 3
Thanks
Thank you sir.
This algorithm dosen't work for duplicate elements.
This method will work for only two element pairs
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..
respect
thank you from israel. u are great.
What??? why need to sort the array first ? Is this the "2 sum" problem ?
thanks i learn
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
Your solution is O(nlog n)
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 algo works for duplicates aswell.. only thing is we have to have sorted array in first place.
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...😞
not a good solution
हिंदी में बोल ले भाई
Waste of time🙄