Split Array Largest Sum - Leetcode 410 - Python

[@NeetCode]

Python - github.com/neetcode-gh/leetcode/blob/main/410-Split-Array-Largest-Sum.py

[@nicolaswolyniec1354]

Link not working 😢

[@devdev19]

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

[@chaoluncai4300]

Indeed. I swear Im not gonna waste 10xtime on lc official solutions anymore, neetcode is the saviour!!

[@niteshmanem1997]

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

[@numberonep5404]

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

[@theantonlulz]

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.

[@李順安-p3x]

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)

[@dpsingh_287]

I did this lol. made a prefix sum array and it ac'd after adding that "micro optimization" mentioned in the video

[@chaoluncai4300]

w

[@iscoto4914]

@@dpsingh_287 can u share the code please?

[@ketangupta1910]

the only way to guess that this is a binary search problem is that in this week leetcode has given all binary search questions🤣🤣🤣

[@abhimanyuambastha2595]

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

[@akshitthakur5179]

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

[@vishalvanpariya1466]

subarray + 1

[@nishantingle1438]

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.

[@shengzhaolei5500]

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.

[@vdyb745]

Mindbender !!! Would have never realized it is a binary search problem !!! Simply Brill !!!!! 👏👏👏🙇‍♂

[@zaidshaikh2536]

Glad you made this video. This problem is indeed Unique in Itself.

[@NeetCode]

True, it's definitely not obvious

[@vijethkashyap151]

❤ Just gratitude man! Best channel ever!

[@koeber99]

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

[@Kidpunk98]

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

[@SweetDarkViolet]

Ohhh here it comes. Last daily challenge of March.

[@NeetCode]

Yeah, this coming sunday I will introduce something cool for the channel - you heard it here first :)

[@darshanputtaswamy3199]

What's that ?

[@mahendar7733]

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

[@JijaChad-os8mo]

Thank you so much bro for your explanations. But with your help, I am gaining some confidence in solving hard problems.

[@nitaikodkani]

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

[@ytsrlee9224]

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.

[@soumikkarmakar7433]

Similar to "Allocate minimum number of pages" problem.

[@nikhilsingh2184]

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

[@shrimpo6416]

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

[@kareni7572]

Thanks for the dp recursive solution!

[@sushantrocks]

similar to fair workload - there we can get the relation to bin search

[@hkanything]

Where is the 37 comes from? 7+2+5+10+18 =42

[@yunshuwang5078]

I double count and confused myself

[@simpendatahapefentira1280]

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)

[@varunsen2802]

Thank you for this solution.

[@NeetCode]

No problem!

[@albertchen5501]

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

[@lambar0]

Neat Code … simple and precise

[@neelmehta9092]

The person who made this problem is evil

[@ritikjain307]

Of topic question, in python is it better to use nested functions or not. How to define different functions and use them.

[@theearthish]

Was waiting for this lol 100% crackhead intuition needed. Amazing explanation as always 🙌

[@josephchen1344]

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?

[@nameless2850]

May be solving after sorting would do?

[@criticstar123]

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

[@soumyadeepdas1536]

It's basically the painters partition problem

[@Chirayu19]

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

[@shikshamishra5668]

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

[@AniketSingh-mt6zr]

classy explanation

[@HardeepSingh-pi2hr]

Am I missing something or is the code working without any return statement inside splitArray method? We should be returning res right?

[@NeetCode]

Good catch, your right - the return statement was cutoff of the screen. Sorry for confusion, added the entire code in a comment above.

[@HardeepSingh-pi2hr]

Ohh not a problem... I thought I was tripping xD

[@HardeepSingh-pi2hr]

And thanks for your hard work. You have a new fan in me 🙌

[@nishantingle1438]

The Optimal solution is a pretty standard variation of Binary Search. Check Allocate Pages from GeeksForGeeks/Aditya Verma's KZbin video or LC 1011.

[@superheroherohero]

Thank you!

[@rongrongmiao3018]

Oh well I was just looking at this problem today

[@DavidDLee]

1. Missing return: code will not run 2. 16:06 missed the mark on explaining the logic back in 10:03

[@koeber99]

Why is the canSplit function ""return (subarry +1

[@prrnnv2]

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

[@i8you]

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

[@Zifox20]

Easy Problem: How many videos do I need before you become my favourite youtuber?

[@yan-vn5oy]

good explanations as aways

[@tenzin8773]

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

[@AbdulAziz-fp3hz]

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

[@uditsharma5688]

When the backtracking solution passed , was it faster than the binary search?

[@NeetCode]

Not even close, binary search is much more efficient

[@italianpipes1849]

Grazie mille!

[@jugalparulekar661]

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

[@jackie0315]

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?

[@anybody413]

Thanks!

[@saurabhkumarsrivastava6034]

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

[@khanhquoc5352]

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.

[@infiniteloop5449]

3 months too late but n is num[I]. for n in nums is going through every value in nums

[@lazydoner6552]

Is this question similar to book allocation problem of ggg?

[@snex-techprogrammer5110]

'return res' at the end

[@sarbajitde2547]

How is the code working without any return statement?

[@anthonyuccello1458]

Solution is O(crackhead)

[@bchen1403]

this is madness

[@sipwhitemocha]

Could someone please help me how R = sum(nums) is initially 37??? 8:55

[@infiniteloop5449]

Crack Head Problems would be an interesting KZbin List.

[@joydeeprony89]

why low = max(nums) ?

[@yashwants18]

Let say if m = len(nums) then what would be the answer? I guess max(nums)

[@alps747]

I couldn't understand the explanation starting at 10:25 (kzbin.info/www/bejne/j4apZJKbd8mtqc0). 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?

[@kongzilla2897]

In constraints it is mentioned that m < nums.size()

[@dokudenpa8207]

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?

[@bouzie8000]

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

[@Shaaah_]

⬇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

[@gokulrajr]

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

[@kaushalkumar-kj9uh]

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