Neet has finally broken out of "Hard Level" brain area and breached into this new area called the "Crackhead zone". He is the first of mankind to reach this point of the brain. I have full confidence that Neet will continue such successful expeditions through the Crackhead zone as he continues to solve more cracked leetcode problems
Other than the weird 37 instead of 42 typo this is a spectacular explanation of the algorithm. Strongly doubt that everyone on LC who post this exact same algorithm actually thought of it themselves.
This problem is exactly same as Leetcode 1011. The same code also works for this. Its just a lot difficult to understand how this problem is similar to 1011
In the DP approach, if you can reduce the time doing "sum(nums[i:])" to O(1) by using some technique like subtraction of two prefix sums, you can actually AC (with poor runtime)
I converted that backtracking solution to a recursive function & then memoized it to make a dp solution & it worked with 10% faster & 90% space efficient. Variation of Matrix Chain Multiplication.
I think that initializing subarray as 1 is better, since we can consider that we create an empty subarray first and then add the item into the subarray; if we initialize as 0, then you need to add 1 as the sum of last subarray is less than largest and you have to count it.
The plus one is needed in canSplit function because leftover in curSum needs to be in it's own "subarray". Therefore " if ( curSum>0 ) subArrays++; " is needed in canSplit function. Then finally line because (subarray +1
Hi NeetCode, What if the question becomes: split an array into m non-empty "subsets" (doesn't need to be continuous) and minimize the maximum sum among these subsets? Can you think of any faster solution than backtracking through all possible combination?
If your code is not working then try returning low after the if else condition at last it was cut down from the video. Returning should solve your problem
Here the count: 18(min , max that we can get in 1 elemen array) .......... 42 (sum for max ). So between 18 and 42 , we find the mid of 27. And 37 is sum of adjusting right grup elemen array
37 definitely comes from an incorrect math or typo. I add print() in his python code and run it with the example he uses in this video. Then I got the first round of (l, r, mid) is (18, 42, 30)
you can always split a subarray into further smaller subarrays without violating the maximum condition, since there is no upper limit on minimum sum of the subarrays
I couldn't understand the explanation starting at 10:25 (th-cam.com/video/YUF3_eBdzsk/w-d-xo.html). Why having two subarrays is not a problem. what if m was 6 and there was no way to split the left subarray into 6 subarrays since it has only 5 elements? Could someone pls explain?
I guess I dont understand how in the "canSplit" function, you can be so greedy? How can you just add numbers from left to right as the array elements? What if the optimal members of the array elements such the sum is less than target is not from left to right?
Hi bro, 1712. Ways to Split Array Into Three Subarrays Could you please explain the binary search and sliding window approach of this leetcode problem...
Wait so this is pretty much identical to 1011. Capacity To Ship Packages Within D Days. How comes one is ranked as hard while the other is ranked as medium?
Python - github.com/neetcode-gh/leetcode/blob/main/410-Split-Array-Largest-Sum.py
Link not working 😢
Whenever Im stuck on a problem, I check if NeetCode has a solution available and like so many times before you came through. Thank you NeetCode
Indeed. I swear Im not gonna waste 10xtime on lc official solutions anymore, neetcode is the saviour!!
Neet has finally broken out of "Hard Level" brain area and breached into this new area called the "Crackhead zone". He is the first of mankind to reach this point of the brain. I have full confidence that Neet will continue such successful expeditions through the Crackhead zone as he continues to solve more cracked leetcode problems
Lovely explanation as usual! You know it's an actual hard problem when the DP solution is the easiest one to come up with :p
Other than the weird 37 instead of 42 typo this is a spectacular explanation of the algorithm. Strongly doubt that everyone on LC who post this exact same algorithm actually thought of it themselves.
the only way to guess that this is a binary search problem is that in this week leetcode has given all binary search questions🤣🤣🤣
This problem is exactly same as Leetcode 1011. The same code also works for this. Its just a lot difficult to understand how this problem is similar to 1011
In the DP approach, if you can reduce the time doing "sum(nums[i:])" to O(1) by using some technique like subtraction of two prefix sums, you can actually AC (with poor runtime)
I did this lol. made a prefix sum array and it ac'd after adding that "micro optimization" mentioned in the video
w
@@dpsingh_287 can u share the code please?
binary search approach of this problem is similar to book allocation problem pattern, just in case someone is wondering about the intuition
I converted that backtracking solution to a recursive function & then memoized it to make a dp solution & it worked with 10% faster & 90% space efficient. Variation of Matrix Chain Multiplication.
I think that initializing subarray as 1 is better, since we can consider that we create an empty subarray first and then add the item into the subarray; if we initialize as 0, then you need to add 1 as the sum of last subarray is less than largest and you have to count it.
Glad you made this video. This problem is indeed Unique in Itself.
True, it's definitely not obvious
subarray + 1
Mindbender !!! Would have never realized it is a binary search problem !!! Simply Brill !!!!! 👏👏👏🙇♂
❤ Just gratitude man! Best channel ever!
The plus one is needed in canSplit function because leftover in curSum needs to be in it's own "subarray". Therefore " if ( curSum>0 ) subArrays++; " is needed in canSplit function. Then finally line because (subarray +1
Thank you so much bro for your explanations. But with your help, I am gaining some confidence in solving hard problems.
Into the first 4 min of video.
I come up with this binary search .
But was struggling with conditions to check the largest number lol
was stuck on this one, thanks a lot for explaining it so well
Am I missing something or is the code working without any return statement inside splitArray method? We should be returning res right?
Good catch, your right - the return statement was cutoff of the screen. Sorry for confusion, added the entire code in a comment above.
Ohh not a problem... I thought I was tripping xD
And thanks for your hard work. You have a new fan in me 🙌
Ohhh here it comes. Last daily challenge of March.
Yeah, this coming sunday I will introduce something cool for the channel - you heard it here first :)
What's that ?
Nice video! For some moment, I came across the searching space, but stuck in the meaning of mid. Thanks for explain the mid and the greedy method.
Of topic question, in python is it better to use nested functions or not. How to define different functions and use them.
Hi NeetCode,
What if the question becomes: split an array into m non-empty "subsets" (doesn't need to be continuous) and minimize the maximum sum among these subsets?
Can you think of any faster solution than backtracking through all possible combination?
May be solving after sorting would do?
Similar to "Allocate minimum number of pages" problem.
If your code is not working then try returning low after the if else condition at last it was cut down from the video. Returning should solve your problem
Thank you for this solution.
No problem!
similar to fair workload - there we can get the relation to bin search
Thanks for the dp recursive solution!
Can we build a prefix sum array and use it somehow to solve the problem greedily or binary search on the same array?
I come up with a break even approach. Let me debug and see if it’s more efficient 🙂
I used brute force method got the ans in the end but it is not optimal algorithm does it matter in interviews
Was waiting for this lol 100% crackhead intuition needed. Amazing explanation as always 🙌
Is it just me, or is 37 the wrong value for initial right? The total sum of numbers is 42.
The person who made this problem is evil
can we do by keep target=sum(nums)//k and finding the split?
hey @NeetCode awesome explanation but i was wondering without return how the answer is returning .. don't we need to write return res ??
hi everyone, I'm the dum dum that uses backtrack without cache 🤣 I'm so glad I learned the bin search solution!
i dont really understand that, in canSplit fuction, to compute sub sum, why we currentSum+= n instead of curSum += num[i]. Thanks for answering me.
3 months too late but n is num[I]. for n in nums is going through every value in nums
Neat Code … simple and precise
Where is the 37 comes from? 7+2+5+10+18 =42
I double count and confused myself
Here the count: 18(min , max that we can get in 1 elemen array) .......... 42 (sum for max ). So between 18 and 42 , we find the mid of 27. And 37 is sum of adjusting right grup elemen array
37 definitely comes from an incorrect math or typo.
I add print() in his python code and run it with the example he uses in this video. Then I got the first round of (l, r, mid) is (18, 42, 30)
Could someone please help me how R = sum(nums) is initially 37??? 8:55
When the backtracking solution passed , was it faster than the binary search?
Not even close, binary search is much more efficient
1. Missing return: code will not run
2. 16:06 missed the mark on explaining the logic back in 10:03
The Optimal solution is a pretty standard variation of Binary Search.
Check Allocate Pages from GeeksForGeeks/Aditya Verma's TH-cam video or LC 1011.
Just wanted to bring the viewers' attention to the missing "return res" statement at the end of the splitArray function.
Why is the canSplit function ""return (subarry +1
you can always split a subarray into further smaller subarrays without violating the maximum condition, since there is no upper limit on minimum sum of the subarrays
Is this question similar to book allocation problem of ggg?
Is this a very hard problem for someone who started DSA about 2 weeks ago?
Oh well I was just looking at this problem today
classy explanation
I couldn't understand the explanation starting at 10:25 (th-cam.com/video/YUF3_eBdzsk/w-d-xo.html). Why having two subarrays is not a problem. what if m was 6 and there was no way to split the left subarray into 6 subarrays since it has only 5 elements? Could someone pls explain?
In constraints it is mentioned that m < nums.size()
It's basically the painters partition problem
I guess I dont understand how in the "canSplit" function, you can be so greedy? How can you just add numbers from left to right as the array elements? What if the optimal members of the array elements such the sum is less than target is not from left to right?
good explanations as aways
Grazie mille!
Thank you!
How is the code working without any return statement?
Easy Problem: How many videos do I need before you become my favourite youtuber?
If i'm asked this question in the interview, I am beyond cooked
What the magic has happened without return res?
Thanks!
I think that it's the same as book allocation problem
'return res' at the end
why low = max(nums) ?
Let say if m = len(nums) then what would be the answer? I guess max(nums)
Solution is O(crackhead)
⬇Simple Code | TC: O( n*log( sum(nums) ) | SC: O( 1 )
int splitArray(vector& nums, int m) {
int l=0,r=0,n=nums.size();
for(int i=0;i
this is madness
Crack Head Problems would be an interesting TH-cam List.
Hi bro,
1712. Ways to Split Array Into Three Subarrays
Could you please explain the binary search and sliding window approach of this leetcode problem...
Lol this is truly a crackhead solution. God help us all
Wait so this is pretty much identical to 1011. Capacity To Ship Packages Within D Days. How comes one is ranked as hard while the other is ranked as medium?
this prob is exactly same :1011. Capacity To Ship Packages Within D Days