Array - 36: Find all Triplets for given Sum | Check if Triplet exists for given Sum
Vložit
- čas přidán 13. 04. 2020
- Source Code:thecodingsimplified.com/find-...
Solution:
- Sort the array
- Take one loop & iterate each element
- Now for each element, you check if there exists a pair whose sum is equal to targetSum - current value
- When you find out value, you add in final list, else you increase start or decrease end depending on value addition
Time Complexity: O(n * n)
Space Complexity: O(1)
Do Watch video for more info
CHECK OUT CODING SIMPLIFIED
/ codingsimplified
★☆★ VIEW THE BLOG POST: ★☆★
thecodingsimplified.com
I started my CZcams channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.
★☆★ SUBSCRIBE TO ME ON CZcams: ★☆★
czcams.com/users/codingsimplif...
★☆★ Send us mail at: ★☆★
Email: thecodingsimplified@gmail.com
Bro your channel is best on youtube for such type of questions which are frequently asked in the interviews. Your content is just crisp and to the point. Same solution is explained by other youtuber in a 30 min video. you managed in 10 min saving our crutial time. I have followed all your array and tree series and tree series is just awesome. In my college days I wish the channel existed my DSA would have been at other level. Anyhow I am learning now. Keep up the good work.
Your way of explaining questions are damn good. I have watched many videos of urs and every time u earn my respect,Sir. Thank you so much.
Thanks for your nice feedback. Keep Watching.
It does not work if array is arr = [5, 5, 4, 4, 5, 4] even after sorting when triplet sum is 13 and size is explicitly 6. plz correct and help us!
Yes
Buddy This will work.
Bhai 2 wala solve kro fir 3 walo pakro...Is ka toh samjh ni aaya But 2 lagaya simple wala toh 3 wala clear ho gya
int[] ar = {1,2,4,5,6};
int target = 6;
for (int i =0; i < ar.length; i++) {
for ( int j = i+1; j < ar.length; j++) {
if((ar[i] + ar[j]) == 6) {
System.out.println(ar[i] + " + " + ar[j] + " = " + (ar[i] + ar[j]) );
}
}
}
----------------------------------------------------------------------------------------------------------------
int[] ar = {1, -2, 0, 5, -1, -4};
int target = 2;
for (int i =0; i < ar.length; i++) {
for ( int j = i+1; j < ar.length; j++) {
for ( int k = j+1; k < ar.length; k++) {
if(( (ar[i]) + (ar[j]) + (ar[k]) ) == 2) {
System.out.println(ar[i] + " + " + ar[j] + " + " + ar[k] + " = " + ( (ar[i]) + (ar[j]) + (ar[k]) ));
}
}
}
}
Thank you for the video!!
Thanks for your nice feedback. Keep Watching.
Bro can you make a video of a roadmap of becoming a developer in the various fields of computer science. eg: a roadmap of how to become an android developer or path of a java developer, what one must learn or do after learning the core concepts of Java. It would be very helpful if you did so because there are so many technologies out there and it really confuses me. Please make a video if you can. I have been following your channel for some time now. thank you.
Sure, I'll try to make on it. Thanks.
I will not work for duplicate elements ,in your example if we one more element 4 then it will get wrong
if you are taking -2 as second case then -3 also will be in arraay whyyou skip those cases that"s why many of us getting error in duplicate element cases ..
one of best approach ive ever seen good and i subscribed
Thanks for your nice feedback. Keep Watching.
Can we use Radix sort to get O(n) instead of O(nlogn) ?
Whatever is best for Sorting, we can us that. But Radix sort is not so famous for sorting. Please follow this article or some other: stackoverflow.com/questions/3539265/why-quicksort-is-more-popular-than-radix-sort#:~:text=Quicksort%20saves%20space%2C%20and%20will,arises%20that%20it%20is%20slower.&text=Radix%20sort's%20efficiency%20%3D%20O(c.n,keys%20in%20input%20key%20set.&text=Radix%20sort%20%3D%2016%20*%206%20%3D%2096%20time%20units.
sir pls make solution using hash also.....
yeah, we can make video using Hash also. Thanks for your suggestion. Will try to make on it.
why
start = i+1
not
start = 0, pls help in understanding, triplets can also be formed with the element before i index
pls reply anyone?
For triplet, we need three numbers,
- Value at index i is 1st value
- Value at index start is 2nd value
- Value at index end is 3rd value
if index is i is 1st value, 2nd value at start can't start from 0, it'll be always i + 1.
Hope it helps you. Thanks.
@@CodingSimplifiedwhy
this code is not working for finding sum of all triplet present in the array.
Can't we get better complexity than O(N^2)??
For this question, this is the best solution I can think & which is of O(N^2).
@@CodingSimplified exactly
what if array is 2 2 2 2 2 2 2 2 2 2 and sum is 6 will it work??
I'm late to answer this question but, the answer is that it won't! This algorithm only works if the list has all unique elements.
Yeah it will
👏
cpp code
vector findTriplets(vectorarr, int n, int K) {
vector final_ans;
set initial_ans;
sort(arr.begin(),arr.end());
for(int i=0;i
nice explanation
Thanks for your nice feedback. Keep Watching.
best explanation
Thanks for your nice feedback. Keep watching.
#include
using namespace std;
bool Triplet(int arr[], int arr_size, int sum)
{
int l, r, m; // for left ,right and middle
sort(arr, arr + arr_size);
for (int i = 0; i < arr_size - 2; i++)
{
l = 0;
r = arr_size - 1;
m = (l + r) / 2;
while (l < r)
{
if (arr[l] + arr[m] + arr[r] == sum)
{
cout
int[] ar = {1, -2, 0, 5, -1, -4};
int target = 2;
for (int i =0; i < ar.length; i++) {
for ( int j = i+1; j < ar.length; j++) {
for ( int k = j+1; k < ar.length; k++) {
if(( (ar[i]) + (ar[j]) + (ar[k]) ) == 2) {
System.out.println(ar[i] + " + " + ar[j] + " + " + ar[k] + " = " + ( (ar[i]) + (ar[j]) + (ar[k]) ));
}
}
}
}