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

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

[VinayK]

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

[tintiniitk]

This approach is O(n.log n).
A much better O(n) approach is using hashmaps.
array -> hashmap <n, count>. 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;
}

[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.

[ankan]

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

[prateektripathi]

describe in words how amazing explanation it is

[dobbyunleashed]

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

[Ankit]

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?

[partapupreetham]

This algorithm fails for duplicate elements

[Rajveer]

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

[akhileshswaroopxisrnnadbt]

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

[snehasisbarat]

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

[akhileshswaroopxisrnnadbt]

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

[bhaskarnaik]

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

[preetsingh]

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

[vikassrivastava]

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

[ankan]

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 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.

[sagaru]

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

[_ritiksharma]

Could you please explain the logic behind this code

[Prophetsarkar]

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

[shilpika]

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?