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.

Getting into a routine of solving these problems,thanks to your videos man, much appreciated

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

Hi, Can you please explain why did you pop the last value from quad? thanks

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

I love when you make tiny errors in your code, it's funny how you react to it

Damn I just finished this problem 1 hour ago, inspired by your 2sum/3sum solution.

Damn, nice solution using recursion!

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?

Not the 4sum i was looking for but not disappointed either

No home but love you bro... you just make problem look soo easy ❤❤❤

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]

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 # 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 l += 1 # if total is less than target value,we need a bigger total # move p pointer forward to make bigger total elif tot 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

@sai_45_4_tech

Ай бұрын

i exactly needed a build up from three sum thank you

I think in while (l just tested with break and I am wrong

@mdazharuddin4684

2 жыл бұрын

If we have 1,2,3,4 Both 1,4 and 2,3 will give 5

Every time I get stuck on leetcode question, I first find your video on youtube rather than check the editorial.

Neet you are a Genius

Could you please help me, why this code is not working for test case [2,2,2,2,2] ?

Thanks, You are just amazing

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!

@DeepakPanwar-gv7rk

Жыл бұрын

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

just now i was thinking to do this problem 😄

can someone explain how the recursion and pop worths here ,kinda not getting what quad.pop() does here or how it works.

@_7__716

2 жыл бұрын

Same question. Haven't run the code but don't see why pop is needed.

@_7__716

2 жыл бұрын

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

@dilip_1997

2 жыл бұрын

@@_7__716 yeah I had to run it and figured it out ,thank you

@qwarlock4126

Жыл бұрын

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

Why quad.pop() in line 13 is required. Can someone please help me with that.

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

@takeuchi5760

6 күн бұрын

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 for (let j = i + 1; j let l = j + 1 let r = nums.length - 1 while (l let sum = nums[i] + nums[j] + nums[l] + nums[r] if (sum > target) { r-- } else if (sum l++ } else { ret.push([nums[i], nums[j], nums[l], nums[r]]) while (nums[l] == nums[l+1] && l l++ } l++ r-- } } while (nums[j] == nums[j+1]) j++ } while (nums[i] == nums[i+1]) i++ } return ret };

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

where is function "helper" defined?

Just now i solved this question 😂 and you uploaded

how can i implement in javascript

What is the time complexity of this algorithm? O(n^3) ? Can anyone give a C++ version of this?

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!

@qwarlock4126

Жыл бұрын

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.

@qwarlock4126

Жыл бұрын

others please chime in if I am wrong

@l3onardo57

11 ай бұрын

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,

Hey bro Didn't understood the case why would you first append l to quad and the pop it.

@armaanhasib9145

5 ай бұрын

Same here, can anyone explain

Can someone please explain why did he pop the values in ksum function??

@qwarlock4126

Жыл бұрын

look at my earlier reply above. He is using backtracking

I was asked this question in an Amazon interview. I guess they ask anything these days at Amazon

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

Nice solution

Rookie number, try 10 sum

@NeetCode

2 жыл бұрын

lmao

Can we write condition if target

My 4sums are never this Neet

What is helper function

i think we can also use a pick and a not pick method using recursion

@wlockuz4467

2 жыл бұрын

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

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

Your videos are really helpful......👍👍👍

dang thats clever

As a beginner, I just do not understand what does quad.pop() do?

@robr4501

2 жыл бұрын

me too, I dont get how does the pop gonna clean up,

@robr4501

2 жыл бұрын

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.

@dbalatero

Жыл бұрын

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 total = nums[i] + nums[j] + nums[left] + nums[right] if total > target: right -= 1 elif total left += 1 else: result.append([nums[i], nums[j], nums[left], nums[right]]) left += 1 while left left += 1 return result

If you notice, this is basically a twist on combination sum 2

What a god.

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?

It been a long time what

are you actually talking that fast or you record it 1.5x speed?

Solution fails on LeetCode at this time of writing likely due to new test cases.

You're wrong about problem interpretation, he distinct requirement refers to indexes, not the array elements.

Algo monster or algoexpert?

nice

Naughty minds😉: +1 for problem title

4? Whats next? 5? This is getting crazy

I have solved 3sum and this was difficult

java solution plz if any buddy has?

why is the range from start to n-k+1

@qwarlock4126

Жыл бұрын

python loops are not inclusive. So he needed the +1 value

@juheehong7445

Жыл бұрын

@@qwarlock4126 why do we need to loop until n-k?

@qwarlock4126

Жыл бұрын

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

@qwarlock4126

Жыл бұрын

This is really really nifty code.. love it.

@qwarlock4126

Жыл бұрын

@@juheehong7445 oops... it is around 9:10

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

im cooked

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 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 if (nums[l] + nums[r] ++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 ++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 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

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 if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j if (j > i + 1 && nums[j] == nums[j - 1]) continue; int start = j + 1; int end = nums.length - 1; while (start 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 while (start start++; end--; } else if (sum 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...

@NeetCode

2 жыл бұрын

Wow for $2000 I might have to make one soon 😉

@krishnachaitanya1265

2 жыл бұрын

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

This will fail if target sum is 0.

Update = the solution is not working.. dont waste your time.

@NeetCode

Жыл бұрын

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)

@alfahimbin7161

Жыл бұрын

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.

@user-fk1wo2ys3b

Жыл бұрын

Update - solution is working

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 { 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 { int twoSum = nums[l] + nums[r]; if( r { r--; continue; } if( twoSum > target) { r--; } else if( twoSum { l++; } else { List list = new ArrayList(); list.add(nums[l]); list.add(nums[r]); res.add(list); l++; r--; } } } return res; } }

@eddiej204

2 жыл бұрын

mate, did your code work with this test case? [1000000000,1000000000,1000000000,1000000000] -294967296

Nice solution