love the advice on don't bother with this if you are preparing just for interviews. Thank you! I'd have probably lost a day on that editorial! Thank you NeetCode!
just wanted to say your videos are extremely easy to understand. i've used your channel for hard daily leetcode questions in the past, and you make it alot easier. i liked your realistic comments in this video as well.
i am preparing for interviews and i came across monotonic stack and queue questions and started banging my head against the wall learning these concepts and trying to solve the questions. I am wondering if Amazon/Google do ask these questions on the final loops especially the amazon final loop
I made the subarray_sums, then heapified it, and then popped "right" elements, I summed up the last "left" elements and returned it. Overall for a time complexity of n^2 + right*log(n^2) = n^2*log(n) but if right is a small number it's more efficient
Hey @NeetCodeIO can you please do an episode on range module LC#715? Trying to understand segment trees and was looking for the Neetcode version. Best explained leetcode ever!! thank you so much for all you do!
a question, I understand we have to mod every sub array sum, but why are we modding the sub array sum again when adding it to the final result? this is not asked in the question.
Actually we don't need to MOD when making subarray sum because question states the max value of n = 1000 and nums[i] = 100, so in worst case we can have all 1000 element values to 100 still the sum of largest subarray which is 1000 will not excess the 32bit int. 1000(1001) / 2 = 500500, but when summing the subarray from left to right, in worst case we have to sum whole subarray i.e 500500 * n ^ 2, which can exceed the 32 bit int limit.
I think there's a problem with your first solution. Using that modulo while creating the sums array would break the sort of the numbers were large enough. The only reason it works still is that the sub array sums will never become that large.
There is also an approach to get n^2 solution. C++ has a convenient std::nth_element which easily removes the need for full sort. I'm sure counting sort also works here
There is an O(N*log(M)) time, where M is the sum of all elements in the array, and O(1) space solution. It involves binary search (which you probably already implemented), and some math to calculate the required subarray sums on the fly instead of having the prefix sum array.
@@6mahine_mein_google Just browse the problem's solutions and search for sliding window, theres a few approaches. It might be tough to grasp at first so I'd recommend spending some time on them. Maybe even using an LLM to chat about the solution and understand what topics are involved.
I know many people will not like this, but the smartest thing to do is realize that there are more common patterns to focus on. Rather than the binary search + sliding window pattern which you will almost never see in an interview. If you are smart enough to understand that approach, you're smart enough to realize there are better ways to spend your time.
@@rjarora I thought if they really want to solve on own only why will the come to the video at first point you didn't knew that's why you came know I hope you understand ,I just said my opinion or how should I tell my opinion then 🤷
love the advice on don't bother with this if you are preparing just for interviews. Thank you! I'd have probably lost a day on that editorial!
Thank you NeetCode!
Neetcode have my kids
just wanted to say your videos are extremely easy to understand. i've used your channel for hard daily leetcode questions in the past, and you make it alot easier. i liked your realistic comments in this video as well.
i am preparing for interviews and i came across monotonic stack and queue questions and started banging my head against the wall learning these concepts and trying to solve the questions. I am wondering if Amazon/Google do ask these questions on the final loops especially the amazon final loop
I made the subarray_sums, then heapified it, and then popped "right" elements, I summed up the last "left" elements and returned it.
Overall for a time complexity of n^2 + right*log(n^2) = n^2*log(n) but if right is a small number it's more efficient
i spent 3-4 hrs on editorials and claude trying to understand and nothing made sense until now
Hey Neetcode! Thank you for doing the daily Questions it really helps!
Today's daily challange was asm !! i came to learn something new! thanks for explaining
Hey @NeetCodeIO can you please do an episode on range module LC#715? Trying to understand segment trees and was looking for the Neetcode version. Best explained leetcode ever!! thank you so much for all you do!
a question, I understand we have to mod every sub array sum, but why are we modding the sub array sum again when adding it to the final result? this is not asked in the question.
Actually we don't need to MOD when making subarray sum
because question states the max value of n = 1000 and nums[i] = 100,
so in worst case we can have all 1000 element values to 100 still the sum of largest subarray which is 1000 will not excess the 32bit int.
1000(1001) / 2 = 500500,
but when summing the subarray from left to right, in worst case we have to sum whole subarray i.e 500500 * n ^ 2, which can exceed the 32 bit int limit.
I think there's a problem with your first solution. Using that modulo while creating the sums array would break the sort of the numbers were large enough. The only reason it works still is that the sub array sums will never become that large.
There is also an approach to get n^2 solution. C++ has a convenient std::nth_element which easily removes the need for full sort. I'm sure counting sort also works here
Can you explain the solution?
@@mahdiadib24 call nth_element twice, first to rearrange elements on [0, size) for "right-1"th, then on range [0, right) for "left-1"
pretty simple problem once you understand the description and separate it into manageable chunks :)
Please cover contest as well.
"don't ask me how to come up with it. I think that's a question for God to be honest" - best moment of today's video. And I completely agree.
I have done it with help of recursion.
Time complexity = O(NlogN)
Space complexity = O(N)
Is it optimal?
There is an O(N*log(M)) time, where M is the sum of all elements in the array, and O(1) space solution. It involves binary search (which you probably already implemented), and some math to calculate the required subarray sums on the fly instead of having the prefix sum array.
Hey, can u share ur solution please
@@6mahine_mein_google Just browse the problem's solutions and search for sliding window, theres a few approaches. It might be tough to grasp at first so I'd recommend spending some time on them. Maybe even using an LLM to chat about the solution and understand what topics are involved.
mate share the solution please
I love you Mr. Code
elegant ash heap solution
I first did the N²LogN then came to see the optimized approach by Neetcode and got the treat
This problem is similar to merge k sorted list.
9:32 2 + 6 = 6 lol
looks like Dijkstra
wtf
People are here for the binary search approach
yes
I know many people will not like this, but the smartest thing to do is realize that there are more common patterns to focus on. Rather than the binary search + sliding window pattern which you will almost never see in an interview.
If you are smart enough to understand that approach, you're smart enough to realize there are better ways to spend your time.
@@NeetCodeIO had that pattern asked for my interview yesterday and i gave n2logn approach and got rejected😢.
True!
@@ashaynaik7540 India ? I assume.
I closed the editorial after seeing the sliding window + binary search soln
You shouldn't directly reveal the solution like this for those who haven't solved.
@@rjarora I thought if they really want to solve on own only why will the come to the video at first point you didn't knew that's why you came know I hope you understand ,I just said my opinion or how should I tell my opinion then 🤷
@@rjarora many are telling binary search as comment btw
@@ashish4k07 i have done this que is O(n^2 nlogn) is it good?
@@harishms5330 n^2logn is fine but n^3logn 🙃
Binary Search ? :(
First
i was here for boinary search solution not this onw
Same buddy
That went over my head so hard