Split Array Largest Sum - Leetcode 410 - Python

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.

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?

this is madness

Just wanted to bring the viewers' attention to the missing "return res" statement at the end of the splitArray function.

'return res' at the end

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.

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.

I come up with a break even approach. Let me debug and see if it’s more efficient 🙂

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

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.

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?

Thank you!

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<=m).

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?

Is this a very hard problem for someone who started DSA about 2 weeks ago?

this prob is exactly same :1011. Capacity To Ship Packages Within D Days

binary search approach of this problem is similar to book allocation problem pattern, just in case someone is wondering about the intuition

good explanations as aways

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.

Grazie mille!

why low = max(nums) ?

Maybe dividing cumsum curve into m even pieces can lead to more efficient solution.

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

Is it just me, or is 37 the wrong value for initial right? The total sum of numbers is 42.

hi everyone, I'm the dum dum that uses backtrack without cache 🤣 I'm so glad I learned the bin search solution!

Neat Code … simple and precise

classy explanation

Is this question similar to book allocation problem of ggg?

It's basically the painters partition problem

can we do by keep target=sum(nums)//k and finding the split?

Why is the canSplit function ""return (subarry +1 <= m)"" and not """return ((subarry +1) == m) """? Don't we need to make sure all the splits can occur? For example, if the target is MAX_INTEGER (in case the sum of nums), then this will be true.

Can we build a prefix sum array and use it somehow to solve the problem greedily or binary search on the same array?

⬇Simple Code | TC: O( n*log( sum(nums) ) | SC: O( 1 )
int splitArray(vector<int>& nums, int m) {
int l=0,r=0,n=nums.size();
for(int i=0;i<n;++i) l=max(l,nums[i]), r+=nums[i];

int mid=0,ans=0;
while(l<=r){
mid=(l+r)/2;
int count=0,tempsum=0;
for(int i=0;i<n;++i){
if(tempsum+nums[i]<=mid) tempsum+=nums[i];
else count++,tempsum=nums[i];
}
count++;

if(count<=m) r=mid-1, ans=mid;
else l=mid+1;
}
return ans;
}

was stuck on this one, thanks a lot for explaining it so well

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

hey @NeetCode awesome explanation but i was wondering without return how the answer is returning .. don't we need to write return res ??

Lol this is truly a crackhead solution. God help us all

How is the code working without any return statement?

I used brute force method got the ans in the end but it is not optimal algorithm does it matter in interviews

Thanks for the dp recursive solution!

If i'm asked this question in the interview, I am beyond cooked

I think that it's the same as book allocation problem

subarray + 1 <= k

This line is because our above code does not add the last subarray, which is not counted in the subarray.

❤ Just gratitude man! Best channel ever!

What the magic has happened without return res?