4 Sum Problem | Leetcode #18
HTML-код
- Опубликовано: 7 сен 2024
- This video explains a very important programming interview problem which is the 4 sum problem.This problem can be solved using multiple techniques and algorithms.I have explained all the approaches using simple examples.I have explained 3 techniques.The first one is just by using simple set which is the brute force approach.The second technique is by using set with 2 pointer technique. This is the best approach in terms of time complexity. The third approach is by using hashmap.This solution iis better than the naive approach.
CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
======================================PLEASE DONATE=============================
🧡 SUPPORT OUR WORK: / techdose
💚 UPI-ID: surya.kahar@ybl
💞JOIN Membership: / @techdose4u
==============================================================================
INSTAGRAM : / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
USEFUL LINKS:
🟠Must do TIPS to ACE Virtual Interview: • 🔴Must do Tips to ACE y...
🟢Best strategy to excel your coding interview: • 🔴Best strategy to exce...
🟡Get your dream job in 1 month: • 🔴Get your dream job in...
🔵How to crack dream job in just 2 months: • How to crack dream job...
🟣7 Days DSA plan: techdose.co.in...
RELATED LINKS:
Perfect subarray: • Perfect subarray | Goo...
Subarray sum equals K: • Subarray sum equals K ...
CODE LINK: techdose.co.in...
first time ever saw the face of legend thank you for your tutorials !!
Welcome 😀
sir i like prefer these type of videos , as in from the rest of your videos that i saw , this one has your face , and i dont know why but these type of videos where i can see the instructors face , help me have better understanding
Noted :)
best explanation on youtube....Everyone on youtube just expalins brutforce approach but no one shows the code like you...HATS OFF
I might not have thought about the complexity of chained elements of hashmap in the interviews. Great!
Now you know tha analysis :)
@@techdose4u yea :D
:)
you are amazing. thank you for the detailed explanation and clear thought and explanation process.
Welcome :)
2nd approach can be done without using set, which will make our time complexity O(n^3) instead of O(n^3)log(n) with this check
while(start < end && arr[start] == arr[start+1]) start++;
while(start < end && arr[end] == arr[end-1]) end--;
This will make sure we don't check 2 sum for same values. Since array is sorted all same values will be adjacent.
So skip the same values until we find new value
Code -
class Solution {
public:
vector fourSum(vector& arr, int target) {
vector ans;
int n = arr.size();
if(n
i found that it can done in o(n^3) ....
Loop through i and j and doing a two pointer approach
👍🏼
First, thanks for all the awesome videos. There could be another approach where it would take O(N^3) time if we first sort the array and then take O(N^2) two sums and iter over the original array to find K - ( i th two sum ) exist in the array and that should take O(N) time for each such operation. So the total complexity should be O(N^3)
this approach gives TLE on leetcode
Thank you so much buddy. Your video is really clear and very good explained... in details! thank you
Welcome :)
Thanks for taking the time to explain the ideas. However, the first continue optimization doesn't seem to be correct. It would not let the 4 pointers work in tandem. Anyway, the set will take care of the duplicates. I have yet to implement the 2 sum one.
In the second approach I think we don't need to use a set to handle the duplicates as we can simply compare the last added quadruple with the current one as you did in the 3rd approach.
in second approach , when sum= target u hv written, left=left+1, what if there is duplicate element in while loop also, how to check for dupliacte element in the innermost (while) loop
This is an amazing explanation. Thank you.
Welcome 😊
Really! Amazing video.....
One more added in liked video.
Great 🔥
Thank you sir.
how much time it takes you to make a one video from code explanation to code writing?
3 days :)
Sir can you explain why we have kept i
No. Because a set of 4 elements should have unique indexed elements.
Thanks for the explanation!
In my opinion the easiest one was the solution with hashtable.
Few days earlier same problem has been asked in DAILYHUNT. I couldn't solve😭
Ohhh....no problem. Maybe this will help in future.
Thank you Tech dose.
Welcome :)
Lovely indeed ! thankyou sir for this.
Insertion in set is considered O(1) amortized, not O(log(n)).
In C++, you cannot insert a vector in the unordered_set without providing a hash function. Insertion in unordered_set is O(1) but insertion in set is O(logN)
great explanation !
Thanks
Great explanation sir..thanks for the explanation.
Welcome :)
love from USA
Thanks 😊
It will be nice if you could mention in which playlist you have a certain video in description of every video
👍🏼
Code translated to Java:
public class Sum4 {
public static List fourSum(int[] nums, int target) {
List resultado = new ArrayList();
int n = nums.length;
if(n < 4)
return resultado;
Arrays.sort(nums);
Map mapa = new HashMap();
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
List lista = new ArrayList();
lista.add(new Pair(i, j));
mapa.put(nums[i] + nums[j], lista);
}
}
for(int i = 0; i < n - 1; i++) {
if(i > 0 && nums[i] == nums[i-1]) continue;
for(int j = i + 1; j < n; j++) {
if(j > i + 1 && nums[j] == nums[j-1]) continue;
int sum = target - nums[i] - nums[j];
if(mapa.get(sum) != null) {
for (Pair pair : mapa.get(sum)) {
int k = pair.getIndex1();
int l = pair.getIndex2();
if(k > j) {
if(!resultado.isEmpty() && resultadoContainsCurrentValues(resultado, nums[i], nums[j], nums[k], nums[l])) {
continue;
}
List temp = new ArrayList();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
temp.add(nums[l]);
resultado.add(temp);
}
}
}
}
}
return resultado;
}
private static boolean resultadoContainsCurrentValues(List resultado, int iValue, int jValue, int kValue, int lValue) {
for (List list : resultado) {
if(list.get(0) == iValue && list.get(1) == jValue && list.get(2) == kValue && list.get(3) == lValue) {
return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(fourSum(new int[]{2,2,2,2,2}, 8));
}
static class Pair {
int index1;
int index2;
public Pair(int index1, int index2) {
super();
this.index1 = index1;
this.index2 = index2;
}
public int getIndex1() {
return index1;
}
public void setIndex1(int index1) {
this.index1 = index1;
}
public int getIndex2() {
return index2;
}
public void setIndex2(int index2) {
this.index2 = index2;
}
}
}
Bro, Aren't you getting overflow error when u submit the code in leetcode if we go with method 2?
thank you so much
awesome!!!!!!!!!!!!!!
Hello sir, your explanation is great. I want to know which software are you using to write on the screen. And also what is your set up, like are you using a tablet and writing on it using stylus or you are writing on the laptop using the mouse cursor?
Great explanation
Thanks ☺️
Thank you!!! This was a great explanation!
A question plz. At 5:14, you said that the big O for set operation is O(lg N). is that true ?
Time Complexity of HashSet Operations: The underlying data structure for HashSet is hashtable. So amortize (average or usual case) time complexity for add, remove and look-up (contains method) operation of HashSet takes O(1) time.
For HashMap.containsKey(), it should be O(1) too. right ?
Avg is O(1) but WC is O(logN)
@@user-oy4kf5wr8l no need to make things complex. Just say O(1). If interviewer asks in detail then explain :)
@@user-oy4kf5wr8l I am not smart 😂
Pls read the leetcode problem carefully. Unique quadruplets doesn't mean unique i,j,k, and l. It means unique n[i], n[j], n[k], and n[l]. Your code is correct but you should have mentioned this way in explanation. Thanks for the answer though.
yes
sec one was good
finally wait is over.
I am currently very busy so couldn't really post frequently. I will try to post atleast 1 per week.
How come insertion in set is LogN. Isn't it amortized O(1)?
Avg O(1)
Plz make this video for python as well
DSA Concepts are same whatever be the language doesn't matter.
why are you using n -4, n-3, n-2, n-1 where does the -4 come from
I love you! I love you!
😊
Reminder ON :)
Great :)
var sum = target - (arr[i] + arr[j]);
Sir there is 2 playlist of hash...
One is hashing with 5 videos and one is with more than 10-15 videos...
I have done this 5 video playlist so is the other playlist continuation of this playlist
No it's not. Other playlist has only problems. It's not a continuation, other videos are pending
Please explain some hard questions in leetcode
I am explaining topicwise. Whether hard or medium. It shall be done.
I would like to join your live course, could you please help me to register?
Yep. You can register when the forms are released.
can someone please suggest best way to implement hashing function for implementing 3rd approach in java as time complexity of custom HashSet depends on how best we can override the hashCode method
if make set at last in method 2 then time complexity will be O(n3 +nlogN)=O(n3) , am I right?
in method 2 if sum == tar why we are only moving only lefft++ , why not r++ or both can anyone explain
some questions about the complexities, for set insertion, hashset insertion should be constant time, isn't it? same constant time for get.
The 3rd approach - generating all the two-sum takes n^2, plus looping through the sums, it's 2* n^2, may not be (n^2 * n ^2)
O(1) is amortized time, meaning average time. But worst case is not the same. For the 3rd approach, your chain length can go to N^2 and you might have to traverse the entire chain for each 2sum. Possible 2sums are N^2. So time is N^4.
@@techdose4u I think xian is right, even if we consider the worst-case we will find all two sums for a single pair (i, j), and the rest of the pairs will do nothing. So we will traverse all N2 pairs and in the worst case, we will end up including all two sums from the map to our answer. So-net operations are the sum of all operations needed to fetch two sums from the map, which is still O(N^2)
EDIT: though making map initially can take O(N^4) in worst case
This an amazing explanation.
How can i contract with you brother?
Second approach 5:27
Thank you so much for such wonderful videos, these videos have helped me learn so much in so little time!
Please explain how the 3 approach takes n^4, I think it takes n^3
If chain length is N^2 and (Target-2sum) = 2sum then you will get N^4.
I am getting signed integer overflow bro for the sum value
tq anna
Welcome :)
Nice
:)
please solve Water Connection Problem on gfg
I guess, Approach 3 will fail in case all elements are same?
No it will work even if all elements are same. But this is worst case situation and the time complexity will become O(N^4)
i am getting runtime error: signed integer overflow:
in this line sum=nums[i]+nums[j]+nums[left]+nums[right];
Define long long int sum,sum1,sum2; instead of int sum and sum1=nums[i]+nums[j];
sum2=nums[left]+nums[right];
sum=sum1+sum2;
It will not give you any error
excellent :)
Thanks :)
Your first code is not running
sir this can be even done through backtracking ryt ❔
will give tle
I change speed from 2x to normal I was not able to identify his voice
😂
BTW MOST OPTIMAL SOLUTION USES NO DATA STRUCTURE
ONLY 2 POINTERS
👌👌
👍🏼
I have done using the second algorithm.But my set is containing duplicate vectors.How is this possible xD
did you sort.
same
Coool
:)
link to buy the mic ?