Two Pointers | Three Sum Problem | C++ Placement Course | Lecture 26.1

Notes of this Lecture:

[shreyashgondane]

I love The Word ' Three Sum' samjh rahe Samjh rahe ho....

[aviralchandra]

Never hoped to see threesum in educational way 🤣🤣🤣🤣🤣

[apoorvo]

Everyone is focused on this word "Three Sum"
while my words are - Please upload the notes of video no. 55, 56, 65 , 66, 67, 69, 70 and so after that also no notes in the description box . So please upload the notes . Thanks

[whereiskhalid]

For Java Folks :)

public static void find3Sum(int[] arr, int target) {
Arrays.sort(arr); // not required if the input is sorted
int n = arr.length;

// used for loop to fix the first element
for (int i = 0; i < n; i++) {
// convert the problem into 2Sum
int low = i+1;
int high = n-1;
while(low < high) {
int curr = arr[i] + arr[low] + arr[high];
if (curr == target) {
System.out.println(arr[i] + " "+arr[low]+" "+arr[high]);
break;
} else if (curr < target) {
low++;
} else {
high--;
}
}

}
}

[ramchhabra]

i am a beginner in c++, i think in the bruteforce approach which i thought on my own one more condition should be there that i!=j and j!=k and k!=i because if they are equal it is taking the sum of same element of the array more than once which should not be there as the repetition of the elements should not be allowed as we want three distinct elements whose sum id equal to the target .
thanks for the video sir .

[SouravMondal-hbrz]

you have to put one more line after line # 16 to prevent infinite loop.i think you have to put low+=1 after line 16

[pranavtiwari_yt]

Can you make a video on how to create cartoonist avatar of a person like Aman Dhatarwal in the thumbnail

[shaileshhacker]

1:01 // Brute force approach


#include<iostream>
#include<vector>
using namespace std;
int main()
{
cout<<"Enter number of elements: ";
int n;
cin>>n;
cout<<"Enter target: ";
int target;
cin>>target;
cout<<"Enter elements:"<<endl;
vector<int> list(n);
for(auto &i:list){
cin>>i;
}
bool found=false;
int arr[3];
for(int i=0; i<list.size(); i++){
for(int j=i+1; j<list.size(); j++){
for(int k=j+1; k<list.size(); k++){

arr[0]=i;
arr[1]=j;
arr[2]=k;
found=true;
break;
}
}
}
}
if(found){
cout<<"Found at index "<<arr[0]<<", "<<arr[1]<<" & "<<arr[2]<<endl;
cout<<list[arr[0]]<<" + "<<list[arr[1]]<<" + "<<list[arr[2]]<<" = "<<target<<endl;
}
else{
cout<<"Not found"<<endl;
}
return 0;
}

[jr.stark]

three element : 1, 3, 1 (in 2nd example)

[anmol_pal]

Pls make videos on other CS topics as well 🙏

[nirajjain]

I didn't get it . You said we are going to use 2 pointer and explain it as well but during the code you found current sum and compared it with target . that part is not clear .please explain it

[anantyadav]

When will you start uploading Java lectures ???

[saumyachoudhary]

can you tell the other algo through which this can be solved

[sach_in_sigma]

Reduce three sum to two sum and peace is achievable 😊

[neilsagarsahu]

Just sort it and apply finding two sum with iteration

[adrishbhattacharya]

Pls clarify if there are more than 1 triplets and u have to find all of them

[MangoLassiYT]

just a question why are we declaring array dynamically

[_ratneshMaurya]

But what if we have duplicate elements in array ... Answers is coming incorrect...
I mean suppose we have to calculate the number of triplets exist in whole array, Let the array be 6, 1, 6, 5, 3, 2, 5, 0, 5, 6, 0 and total number of triplets that should exist is 5, , but according to your code the answer is 3 ...
So my question is how to handle for duplicates....
Waiting for your answer...

[noedie]

for some reason it wont prompt me for array input even tho i've practically written the same code!

[JSDev]

ek hashmap lelo toh top level loop ki zaroorat nhi h, complexity ho jayegi NlogN with extra space N