Split Array Largest Sum - Leetcode 410 - Python

0:00 - Read the problem
2:10 - Explain Brute Force & DP
4:32 - Memoization Code
5:10 - Explain Binary Search
12:21 - Coding Binary Search

leetcode 410

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[devdev]

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

[niteshmanem]

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

[poptart-br]

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.

[李順安-px]

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)

[ketangupta]

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

[akshitthakur]

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

[zaidshaikh]

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

[vdyb]

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

[shengzhaolei]

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.

[nishantingle]

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.

[vijethkashyap]

❤ Just gratitude man! Best channel ever!

[nitaikodkani]

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

[mahendar]

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

[vishalvanpariya]

subarray + 1 <= k

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

[ytsrlee]

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.

[JijaChad-osmo]

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

[soumikkarmakar]

Similar to "Allocate minimum number of pages" problem.

[theearthish]

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

[DavidDLee]

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