I was doing the same question.. and later searched for your explanation and amazed to see it was uploaded just 8 mins ago. Felt like you just uploaded it for me😅😂
Thanks so much for taking the time to help us all out here. This is the rare use case for a do while loop, the two sum level repeat digit loop. Since we definitely want to move the pointer at least once but maybe more times.
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: # sort array,this way we can safely ignore repeating values # because after sort,same values come one after one nums.sort() result = [] for i in range(len(nums)): # if repeating value,ignore the value if i > 0 and nums[i] == nums[i - 1]: continue # solve 3sum problem with nums[i] for j in range(i + 1, len(nums)): if j > i + 1 and nums[j] == nums[j - 1]: continue # solve 2sum problem with nums[i]+nums[j] l = j + 1 r = len(nums) - 1 while l < r: # if total sum of 4 numbers equal to target,append to result list tot = nums[i] + nums[j] + nums[l] + nums[r] if tot == target: result.append([nums[i], nums[j], nums[l], nums[r]]) l+=1 while l < r and nums[l] == nums[l - 1]: l += 1 # if total is less than target value,we need a bigger total # move p pointer forward to make bigger total elif tot < target: l += 1 # if total is bigger than target value,we need a smaller total # move q pointer backward to make small total else: r -= 1 return result
One of my favourite Neetcode videos! because I always wondered same question -> "How to solve a problem, where for each inrement, we would need a new for loop", this video is just perfect!
It does but that's an easier thing. You can figure out the set solution from the no set solution pretty easily, but if you only know the set solution, you're gonna have a hard time if the interviewer asks for the no set solution.
Here's the 3+1Sum solution. Honestly I'll stick to this, since it's pretty much two problems for the price of one. Plus recursion is hard. /** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum = function(nums, target) { if (nums == null || nums.length == 0) { return [] } nums.sort((a,b)=> a-b) let ret = [] for (let i = 0; i < nums.length - 3; i++) { for (let j = i + 1; j < nums.length - 2; j++) { let l = j + 1 let r = nums.length - 1 while (l < r) { let sum = nums[i] + nums[j] + nums[l] + nums[r] if (sum > target) { r-- } else if (sum < target) { l++ } else { ret.push([nums[i], nums[j], nums[l], nums[r]]) while (nums[l] == nums[l+1] && l < r) { l++ } l++ r-- } } while (nums[j] == nums[j+1]) j++ } while (nums[i] == nums[i+1]) i++ } return ret };
Could you also upload the solutions in C++, your videos are really helpful but having the option to understand them in other popular languages like C++ will be a great help for many of us out there. Thanks
@@armaanhasib9145 @m04d10y1996 I think to have the next loop run correctly. So after i = 0 and we get the values we need for it, we need to move with i to 1 and get the other 3 values as well.
Hi, I have a confusion regarding the position of "return" statement. From what I learned, we should put "return" at the end of the base case. However, I'm quite confused that in this question it can pass no matter we put "return" at the end of general case (like Neetcode did in the video), or at the end of the base case (k==2), or without "return" statement inside nSum function. Can someone help to explain this? tysm!
It needs a return statement after the end of k!=2 section or else it'll continue executing the rest of the code. Or you can put the other half of the code in the else block then you won't be needing the return statement. And also the the res and quad variables are in the foursum function not kSun function so whenever kSum is trying to add values to those variables it's doing it to quad and res of the foursum variables so in the end kSum is giving out values to the foursum variables. So it doesn't need a return statement
I think in while (l < r) when you find a solution (in else) you can break the loop, because i do not think you can find another solution because the array is sorted and you do not want duplicate --> just tested with break and I am wrong
I think there's a bug for 5sum, where the input is 1,2,3,4,4,5 and sum is 14. It will take 1,2,3 since they not duplicate, but before the row 25, it will select 4,4 after it tried to take 4,5. Another if is needed before row 23, to check if nums[l]!=nums[r]
This is backtracking. He is adding the number... then calling recursive. the pop you only get if this is the wrong track. So he added nums[i] then since this is the wrong track... he pops it back off. he removes it from quad. again he only gets to this code if he did not find the right track. Look up backtracking examples.
Actually I think the pop happens whether it is the “right” track or the “wrong” track. When you do quad.append(nums[i)], it is taking that number as the current candidate for the kth element. Then you run a recursive call to check the possible answers given that this is ur kth candidate. When you pop that number off, it allows you to move on to the next candidate for the kth element. By using quad as a global-ish variable in this scope, all candidates are stored in one variable. So there isn’t extra space needed to store other candidates,
nice explanations! but would there be a more efficient way, such that we can know that the values we have so far is for sure impossible to get a solution , so we can terminate earlier?
I figureed out, the quad is a temperory array that contains 2 of the 4 sum, eg . [1 , 2]. and it has to be cleaned up to empty for the possible other combinations of pairs and adds up to possible solution.
I think the temporary array and recursion, while neat, adds confusing elements that makes it harder to grok. Personally I think an iterative solution reads better, and doesn't require that much duplication (or a temporary array): class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() result = [] for i in range(0, len(nums) - 3): if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1, len(nums) - 2): if j > i + 1 and nums[j] == nums[j - 1]: continue left = j + 1 right = len(nums) - 1 while left < right: total = nums[i] + nums[j] + nums[left] + nums[right] if total > target: right -= 1 elif total < target: left += 1 else: result.append([nums[i], nums[j], nums[left], nums[right]]) left += 1 while left < right and nums[left] == nums[left - 1]: left += 1 return result
Is this code working for when we have 3 similar consequetive values? This is the example below- Input - [-1, 0, -5, -2, -2, -4, 0, 1, -2] target - (-9) output from this code - [[-1,-4,-5,1],[-4,-5,0,0]] expected output - [[-5,-4,-1,1],[-5,-4,0,0],[-5,-2,-2,0],[-4,-2,-2,-1]] Can someone help?
C++ solution: #include #include #include using namespace std; vector res; vector quad; vector nums; // Function to find k sum void kSum(int k, int start, int target) { if (k != 2) { for (int i = start; i < nums.size() - k + 1; ++i) { if (i > start && nums[i] == nums[i - 1]) continue; quad.push_back(nums[i]); kSum(k - 1, i + 1, target - nums[i]); quad.pop_back(); } return; } int l = start, r = nums.size() - 1; while (l < r) { if (nums[l] + nums[r] < target) ++l; else if (nums[l] + nums[r] > target) --r; else { res.push_back(quad); res.back().push_back(nums[l]); res.back().push_back(nums[r]); ++l; while (l < r && nums[l] == nums[l - 1]) ++l; } } } vector fourSum(vector& nums, int k, int target) { sort(nums.begin(), nums.end()); kSum(k, 0, target); return res; } int solve() { int n, k, target; cin >> n >> k >> target; for (int i = 0; i < n; i++) { int a; cin >> a; nums.push_back(a); } vector result = fourSum(nums, k, target); // Print the result for (const auto& quad : result) { for (int num : quad) { cout
@@juheehong7445 k is how many values you need. So you could just loop the whole range but once you are past len(nums) -k+1 you dont have room enough left to form your quads. or triplets or... rewatch at 9:40. That has the place where he talks about that part.
Yay I was hoping you would make a video about this one! Thanks :) Do you mind doing one about A*? Sorry if you did one already, I will find it eventually :p
I did it like 3sum import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public List fourSum(int[] nums, int target) { Arrays.sort(nums); List result = new ArrayList(); for (int i = 0; i < nums.length - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < nums.length - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; int start = j + 1; int end = nums.length - 1; while (start < end) { long sum = (long)nums[i] + nums[j] + nums[start] + nums[end]; if (sum == target) { result.add(Arrays.asList(nums[i], nums[j], nums[start], nums[end])); while (start < end && nums[start] == nums[start + 1]) start++; while (start < end && nums[end] == nums[end - 1]) end--; start++; end--; } else if (sum < target) { start++; } else { end--; } } } } return result; } }
Hey neet if you are seeing this comment can you please make a complete DSA course ? I would be ready to pay 2000$ for that .. which includes topics and algorithms like trees , graph , dp , trie etc...
Hey anant even i spent same amount on a course recently and it got me placed as well. I can help you in suggesting best paid courses with placement assistance mentorship, TA support, community help, lot more. Feel free to reach out to me. You can find my details in about section of my youtube profile. 😊
Are you sure this solution is not working? github.com/neetcode-gh/leetcode/blob/main/python/0018-4sum.py (also available in multiple languages on neetcode.io)
The solution he showed in the video is not working (its been 9 months so leetcode has changed test cases.) but the solution he has given in his website is working.
I was doing the same question.. and later searched for your explanation and amazed to see it was uploaded just 8 mins ago. Felt like you just uploaded it for me😅😂
Your videos and visual explanations are waaaaaay better than leetcode premium !!! Fantastic ! Thank you so much.
15:45 we can even skip repeatitive r's like
while l
I subscribed to your channel and now because of you i started leetcode.
nothing like a cup of coffee and Neetcode to start a day
Thanks so much for taking the time to help us all out here.
This is the rare use case for a do while loop, the two sum level repeat digit loop. Since we definitely want to move the pointer at least once but maybe more times.
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
# sort array,this way we can safely ignore repeating values
# because after sort,same values come one after one
nums.sort()
result = []
for i in range(len(nums)):
# if repeating value,ignore the value
if i > 0 and nums[i] == nums[i - 1]:
continue
# solve 3sum problem with nums[i]
for j in range(i + 1, len(nums)):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# solve 2sum problem with nums[i]+nums[j]
l = j + 1
r = len(nums) - 1
while l < r:
# if total sum of 4 numbers equal to target,append to result list
tot = nums[i] + nums[j] + nums[l] + nums[r]
if tot == target:
result.append([nums[i], nums[j], nums[l], nums[r]])
l+=1
while l < r and nums[l] == nums[l - 1]:
l += 1
# if total is less than target value,we need a bigger total
# move p pointer forward to make bigger total
elif tot < target:
l += 1
# if total is bigger than target value,we need a smaller total
# move q pointer backward to make small total
else:
r -= 1
return result
i exactly needed a build up from three sum thank you
Every time I get stuck on leetcode question, I first find your video on youtube rather than check the editorial.
while(nums[l]==nums[l-1]) in the base case can give seg fault in cpp, it should be while(l
One of my favourite Neetcode videos! because I always wondered same question -> "How to solve a problem, where for each inrement, we would need a new for loop", this video is just perfect!
Not the 4sum i was looking for but not disappointed either
an easy way to deal with duplicates is to add the quadruplets to a set and convert to a list later. Saves time in interviews
It does but that's an easier thing. You can figure out the set solution from the no set solution pretty easily, but if you only know the set solution, you're gonna have a hard time if the interviewer asks for the no set solution.
Getting into a routine of solving these problems,thanks to your videos man, much appreciated
Here's the 3+1Sum solution. Honestly I'll stick to this, since it's pretty much two problems for the price of one. Plus recursion is hard.
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
if (nums == null || nums.length == 0) {
return []
}
nums.sort((a,b)=> a-b)
let ret = []
for (let i = 0; i < nums.length - 3; i++) {
for (let j = i + 1; j < nums.length - 2; j++) {
let l = j + 1
let r = nums.length - 1
while (l < r) {
let sum = nums[i] + nums[j] + nums[l] + nums[r]
if (sum > target) {
r--
} else if (sum < target) {
l++
} else {
ret.push([nums[i], nums[j], nums[l], nums[r]])
while (nums[l] == nums[l+1] && l < r) {
l++
}
l++
r--
}
}
while (nums[j] == nums[j+1]) j++
}
while (nums[i] == nums[i+1]) i++
}
return ret
};
can someone explain how the recursion and pop worths here ,kinda not getting what quad.pop() does here or how it works.
Same question. Haven't run the code but don't see why pop is needed.
Oh wait. I think the .pop clear the quad array after the recursive calls return and then iterate to add the two next unique values to quad
@@_7__716 yeah I had to run it and figured it out ,thank you
@@dilip_1997 I think you only hit this code when one of the recusive calls go down the wrong path. So it removes that element
No home but love you bro... you just make problem look soo easy ❤❤❤
Could you also upload the solutions in C++, your videos are really helpful but having the option to understand them in other popular languages like C++ will be a great help for many of us out there. Thanks
This is so much better than LC's editorials.
I love when you make tiny errors in your code, it's funny how you react to it
Hi,
Can you please explain why did you pop the last value from quad?
thanks
as we move forward we gotta remove element from left so we can add further elements keeping it a quad
Hey bro
Didn't understood the case why would you first append l to quad and the pop it.
Same here, can anyone explain
@@armaanhasib9145 @m04d10y1996 I think to have the next loop run correctly. So after i = 0 and we get the values we need for it, we need to move with i to 1 and get the other 3 values as well.
Hi, I have a confusion regarding the position of "return" statement. From what I learned, we should put "return" at the end of the base case. However, I'm quite confused that in this question it can pass no matter we put "return" at the end of general case (like Neetcode did in the video), or at the end of the base case (k==2), or without "return" statement inside nSum function. Can someone help to explain this? tysm!
It needs a return statement after the end of k!=2 section or else it'll continue executing the rest of the code. Or you can put the other half of the code in the else block then you won't be needing the return statement. And also the the res and quad variables are in the foursum function not kSun function so whenever kSum is trying to add values to those variables it's doing it to quad and res of the foursum variables so in the end kSum is giving out values to the foursum variables. So it doesn't need a return statement
Neet you are a Genius
Rookie number, try 10 sum
lmao
Damn, nice solution using recursion!
where is function "helper" defined?
I think in while (l < r) when you find a solution (in else) you can break the loop, because i do not think you can find another solution because the array is sorted and you do not want duplicate --> just tested with break and I am wrong
If we have 1,2,3,4
Both 1,4 and 2,3 will give 5
Could you please help me, why this code is not working for test case [2,2,2,2,2] ?
I think this is similar to finding the subsequences that sum to target we just need to check that the length is equal to 4
Damn I just finished this problem 1 hour ago, inspired by your 2sum/3sum solution.
I think there's a bug for 5sum, where the input is 1,2,3,4,4,5 and sum is 14. It will take 1,2,3 since they not duplicate, but before the row 25, it will select 4,4 after it tried to take 4,5.
Another if is needed before row 23, to check if nums[l]!=nums[r]
So there is no way to optimize this beyond the two-sum part? If you had 5sum it would be n^3, 6sum would be n^4 etc.?
If you notice, this is basically a twist on combination sum 2
I was expecting a different kind of 4sum, this cool too though
can we use dfs for this ?
Just now i solved this question 😂 and you uploaded
just now i was thinking to do this problem 😄
Thank you for the great explanation, but what are you doing with quad.pop() at line 13? My C# code doesn't work with this!
This is backtracking. He is adding the number... then calling recursive. the pop you only get if this is the wrong track. So he added nums[i] then since this is the wrong track... he pops it back off. he removes it from quad. again he only gets to this code if he did not find the right track. Look up backtracking examples.
others please chime in if I am wrong
Actually I think the pop happens whether it is the “right” track or the “wrong” track. When you do quad.append(nums[i)], it is taking that number as the current candidate for the kth element. Then you run a recursive call to check the possible answers given that this is ur kth candidate. When you pop that number off, it allows you to move on to the next candidate for the kth element. By using quad as a global-ish variable in this scope, all candidates are stored in one variable. So there isn’t extra space needed to store other candidates,
nice explanations! but would there be a more efficient way, such that we can know that the values we have so far is for sure impossible to get a solution , so we can terminate earlier?
My 4sums are never this Neet
As a beginner, I just do not understand what does quad.pop() do?
me too, I dont get how does the pop gonna clean up,
I figureed out, the quad is a temperory array that contains 2 of the 4 sum, eg . [1 , 2]. and it has to be cleaned up to empty for the possible other combinations of pairs and adds up to possible solution.
I think the temporary array and recursion, while neat, adds confusing elements that makes it harder to grok. Personally I think an iterative solution reads better, and doesn't require that much duplication (or a temporary array):
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
result = []
for i in range(0, len(nums) - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums) - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left = j + 1
right = len(nums) - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total > target:
right -= 1
elif total < target:
left += 1
else:
result.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
return result
I was asked this question in an Amazon interview. I guess they ask anything these days at Amazon
Thanks, You are just amazing
Can someone please explain why did he pop the values in ksum function??
look at my earlier reply above. He is using backtracking
My God. How am I supposed to come up with this, explain and write code passing all test cases in 20 minutes in an interview. 😢
Why quad.pop() in line 13 is required. Can someone please help me with that.
its to clean up the quad array before the next recursive call
i cant seem to wrap my head around why you are subtracting k from len(nums) in the for loop
i think we can also use a pick and a not pick method using recursion
Yep but there are two problems with it,
1. The complexity would be 2^n where n is the number of elements
2. Avoiding duplicates could be tricky
Nice solution
Is this code working for when we have 3 similar consequetive values?
This is the example below-
Input - [-1, 0, -5, -2, -2, -4, 0, 1, -2]
target - (-9)
output from this code - [[-1,-4,-5,1],[-4,-5,0,0]]
expected output - [[-5,-4,-1,1],[-5,-4,0,0],[-5,-2,-2,0],[-4,-2,-2,-1]]
Can someone help?
Naughty minds😉: +1 for problem title
What is helper function
how can i implement in javascript
are you actually talking that fast or you record it 1.5x speed?
C++ solution:
#include
#include
#include
using namespace std;
vector res;
vector quad;
vector nums;
// Function to find k sum
void kSum(int k, int start, int target) {
if (k != 2) {
for (int i = start; i < nums.size() - k + 1; ++i) {
if (i > start && nums[i] == nums[i - 1])
continue;
quad.push_back(nums[i]);
kSum(k - 1, i + 1, target - nums[i]);
quad.pop_back();
}
return;
}
int l = start, r = nums.size() - 1;
while (l < r) {
if (nums[l] + nums[r] < target)
++l;
else if (nums[l] + nums[r] > target)
--r;
else {
res.push_back(quad);
res.back().push_back(nums[l]);
res.back().push_back(nums[r]);
++l;
while (l < r && nums[l] == nums[l - 1])
++l;
}
}
}
vector fourSum(vector& nums, int k, int target) {
sort(nums.begin(), nums.end());
kSum(k, 0, target);
return res;
}
int solve() {
int n, k, target;
cin >> n >> k >> target;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
nums.push_back(a);
}
vector result = fourSum(nums, k, target);
// Print the result
for (const auto& quad : result) {
for (int num : quad) {
cout
Can we write condition
if target
no bcas the target can be -ve acc to the question
4? Whats next? 5? This is getting crazy
What is the time complexity of this algorithm? O(n^3) ? Can anyone give a C++ version of this?
Your videos are really helpful......👍👍👍
Solution fails on LeetCode at this time of writing likely due to new test cases.
why is the range from start to n-k+1
python loops are not inclusive. So he needed the +1 value
@@qwarlock4126 why do we need to loop until n-k?
@@juheehong7445 k is how many values you need. So you could just loop the whole range but once you are past len(nums) -k+1 you dont have room enough left to form your quads. or triplets or... rewatch at 9:40. That has the place where he talks about that part.
This is really really nifty code.. love it.
@@juheehong7445 oops... it is around 9:10
I have solved 3sum and this was difficult
Yay I was hoping you would make a video about this one! Thanks :) Do you mind doing one about A*? Sorry if you did one already, I will find it eventually :p
im cooked
It been a long time what
I did it like 3sum
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List fourSum(int[] nums, int target) {
Arrays.sort(nums);
List result = new ArrayList();
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int start = j + 1;
int end = nums.length - 1;
while (start < end) {
long sum = (long)nums[i] + nums[j] + nums[start] + nums[end];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[start], nums[end]));
while (start < end && nums[start] == nums[start + 1]) start++;
while (start < end && nums[end] == nums[end - 1]) end--;
start++;
end--;
} else if (sum < target) {
start++;
} else {
end--;
}
}
}
}
return result;
}
}
What a god.
bro said 3sum at 0:15
Algo monster or algoexpert?
dang thats clever
Hey neet if you are seeing this comment can you please make a complete DSA course ? I would be ready to pay 2000$ for that .. which includes topics and algorithms like trees , graph , dp , trie etc...
Wow for $2000 I might have to make one soon 😉
Hey anant even i spent same amount on a course recently and it got me placed as well. I can help you in suggesting best paid courses with placement assistance mentorship, TA support, community help, lot more. Feel free to reach out to me. You can find my details in about section of my youtube profile. 😊
5sum5furious
Dang it! I made number of likes 421
I have a little problem...
I need to solve 10 sum
Im not jokinng, if someone can help - please do it
nice
java solution plz if any buddy has?
This will fail if target sum is 0.
Update = the solution is not working.. dont waste your time.
Are you sure this solution is not working? github.com/neetcode-gh/leetcode/blob/main/python/0018-4sum.py
(also available in multiple languages on neetcode.io)
The solution he showed in the video is not working (its been 9 months so leetcode has changed test cases.) but the solution he has given in his website is working.
Update - solution is working
You're wrong about problem interpretation, he distinct requirement refers to indexes, not the array elements.
Got it
class Solution {
public List fourSum(int[] nums, int target) {
Arrays.sort(nums);
return ksum(4,0, nums, target);
}
public List ksum(int k, int start, int[] nums, int target)
{
List res = new ArrayList();
if(k!=2)
{
int kLen = (nums.length)- (k - 1);
for(int i=start; i < kLen; i++)
{
if( i >start && nums[i]==nums[i-1])
{
continue;
}
List temp = ksum(k-1,i+1, nums, target-nums[i]);
for(List t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
}
else{
int l = start;
int r= nums.length-1;
while(l < r)
{
int twoSum = nums[l] + nums[r];
if( r < nums.length-1 && nums[r] == nums[r+1])
{
r--;
continue;
}
if( twoSum > target)
{
r--;
}
else if( twoSum < target)
{
l++;
}
else
{
List list = new ArrayList();
list.add(nums[l]);
list.add(nums[r]);
res.add(list);
l++;
r--;
}
}
}
return res;
}
}
mate, did your code work with this test case?
[1000000000,1000000000,1000000000,1000000000]
-294967296
Nice solution