4 sum, 5 sum the questions can be formed for any sum. But these kinds of questions do not make any sense. What would they test additionally? The logic, the implementation details that you wanna check can very well be tested using 2 sum and at the max 3-sum. After that you just have to keep nesting and getting bogged down.
It used to be the same for me too , but keep solving more questions(check solutions if you can’t solve) and eventually you’ll be able to understand the questions and you’ll eventually start solving the questions on your own as well
def fourSum(nums: List[int], target: int) -> List[List[int]]: n = len(nums) # size of the array ans = [] # sort the given array: nums.sort() # calculating the quadruplets: for i in range(n): # avoid the duplicates while moving i: if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1, n): # avoid the duplicates while moving j: if j > i + 1 and nums[j] == nums[j - 1]: continue # 2 pointers: k = j + 1 l = n - 1 while k < l: _sum = nums[i] + nums[j] + nums[k] + nums[l] if _sum == target: temp = [nums[i], nums[j], nums[k], nums[l]] ans.append(temp) k += 1 l -= 1 # skip the duplicates: while k < l and nums[k] == nums[k - 1]: k += 1 while k < l and nums[l] == nums[l + 1]: l -= 1 elif _sum < target: k += 1 else: l -= 1 return ans if __name__ == '__main__': nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1] target = 9 ans = fourSum(nums, target) print("The quadruplets are:") for it in ans: print("[", end="") for ele in it: print(ele, end=" ") print("]", end=" ") print()
shame we can't see the code enough to see whether it's correct. Specifically, how is the fourth index (d) decided from the hashtable? i,j,k are naturally distinct, all you'd need to check is that "d" > k. The whole thing depends subtly on the hashes' mapped value being overwritten with the highest index in case of duplicates
The hashmap here is used the same way it would be used in two sum or three sum. In the innermost loop, calculate target_value - sum of current triplet. Then check if that difference is in the hash table. If it is, then you have a 4-sum.
Yeah, allocate an array of indices of size n. Start it with values 0 to n-1. Check if all the values at those indices summ to target. Advance the last index by one, if it hits the end of the list add one to the previous index and bring this back to the index after that. Etc Run till you end up advancing the last index to it's final valid position
Just wrote Nsum(n, nums, total) literally just did exactly what I described. It's actually simpler than his 4sum lol. I only have 3 loops, not 4 and nothing has to check if it's on the same index because the indices all move in a way that makes sense, as opposed to just all moving everywhere. That was a fun little exercise tho. Each cycle of your main loop, you check if the mapped numbers in nums sum your total. Then run a for loop on the array of indices going backwards, where you check if you have space to advance, if you can, do it, and then iterate forward pulling the indices back to the spaces just ahead of where you just advanced too. Return your result when your first index is at the length of nums - n.
I saw a comment of someone asking for an nsum function. Its actually pretty easy, and honestly, id say my solution is cleaner than this 4sum solution. It was pretty fun to solve, give it a shot.
Could u please start adding some kinf of debug to your videos? Im pretty sure it will be easier for us to understand these. E.g. X+2 # 4 for x=2 Or how else you want 😅
My mind went for other two sum three some and foursum
3 sum is popular in the hub
Man of culture😂
Hub mean GitHub right
right...?
@@crissdell culture what bro? he meant github bro 😂
I don't git it 😂
Trust me , i've heard about 4sum
There is an O(n^2) solution as well. I know because I screwed up and interview because of this wuestion figured out 😔
4 sum, 5 sum the questions can be formed for any sum. But these kinds of questions do not make any sense. What would they test additionally? The logic, the implementation details that you wanna check can very well be tested using 2 sum and at the max 3-sum. After that you just have to keep nesting and getting bogged down.
There is a proof to show that 2k- Sum can be solved efficiently in O(n^(k/2) * log n) So 4 Sum can be done quadratic.
You’ve probably heard of 2 skin, you might have heard of 3 skin, but have you heard of… well, heh, erm how do I say…
Honestly, great joke
We can use 2 nested loops and a while loop for the 2 pointers
To do what?
Or rather how?
I can't be able to understand the question properly due to very different and difficult way of asking question on leetcode and other coding problems
Me too struggling with same
It used to be the same for me too , but keep solving more questions(check solutions if you can’t solve) and eventually you’ll be able to understand the questions and you’ll eventually start solving the questions on your own as well
@@akshathsb4601 Okay Thanks Bro
It's O(n^3*logn) but can be made with o(n^3)
Can you share the approach?
def fourSum(nums: List[int], target: int) -> List[List[int]]:
n = len(nums) # size of the array
ans = []
# sort the given array:
nums.sort()
# calculating the quadruplets:
for i in range(n):
# avoid the duplicates while moving i:
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n):
# avoid the duplicates while moving j:
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# 2 pointers:
k = j + 1
l = n - 1
while k < l:
_sum = nums[i] + nums[j] + nums[k] + nums[l]
if _sum == target:
temp = [nums[i], nums[j], nums[k], nums[l]]
ans.append(temp)
k += 1
l -= 1
# skip the duplicates:
while k < l and nums[k] == nums[k - 1]:
k += 1
while k < l and nums[l] == nums[l + 1]:
l -= 1
elif _sum < target:
k += 1
else:
l -= 1
return ans
if __name__ == '__main__':
nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1]
target = 9
ans = fourSum(nums, target)
print("The quadruplets are:")
for it in ans:
print("[", end="")
for ele in it:
print(ele, end=" ")
print("]", end=" ")
print()
how is the return type in list of lists and the solution in a set of tuples?
use two nested loop and then two pointers using while loop
Yep this is actually a better strategy:)
Can we not put the values into a set then sliding window style sum all the values([i:i+3])? Making the time O(n)? I might be wrong though!
Wouldn't that just give all contiguous quadruplets only?
shame we can't see the code enough to see whether it's correct. Specifically, how is the fourth index (d) decided from the hashtable? i,j,k are naturally distinct, all you'd need to check is that "d" > k. The whole thing depends subtly on the hashes' mapped value being overwritten with the highest index in case of duplicates
The hashmap here is used the same way it would be used in two sum or three sum.
In the innermost loop, calculate target_value - sum of current triplet. Then check if that difference is in the hash table. If it is, then you have a 4-sum.
This guy only really heard of a 1sum
Let’s just say we all thought of the same thing when he said three sum and four sum 😂
it's a hot topic on the hub bro. i mean github
Foursome 💀
Can you do an nsum? For an arbitrary positive integer n
Yeah, allocate an array of indices of size n. Start it with values 0 to n-1.
Check if all the values at those indices summ to target.
Advance the last index by one, if it hits the end of the list add one to the previous index and bring this back to the index after that. Etc
Run till you end up advancing the last index to it's final valid position
Just wrote Nsum(n, nums, total) literally just did exactly what I described. It's actually simpler than his 4sum lol. I only have 3 loops, not 4 and nothing has to check if it's on the same index because the indices all move in a way that makes sense, as opposed to just all moving everywhere. That was a fun little exercise tho.
Each cycle of your main loop, you check if the mapped numbers in nums sum your total. Then run a for loop on the array of indices going backwards, where you check if you have space to advance, if you can, do it, and then iterate forward pulling the indices back to the spaces just ahead of where you just advanced too.
Return your result when your first index is at the length of nums - n.
Three sum has the same logic as 4sum
Yeah pretty similar.
I saw a comment of someone asking for an nsum function. Its actually pretty easy, and honestly, id say my solution is cleaner than this 4sum solution. It was pretty fun to solve, give it a shot.
Could u please start adding some kinf of debug to your videos? Im pretty sure it will be easier for us to understand these. E.g.
X+2 # 4 for x=2
Or how else you want 😅
No, but I know I'm handsome
create pairs => quadratic. store value => unique pairs, you are done.
Nice one! That's faster