Maximum Sum Circular Subarray - Leetcode 918 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/maximum...
0:00 - Read the problem
1:10 - Kadane's Explanation
5:00 - Circular Explanation
14:00 - Coding Explanation
leetcode 918
#neetcode #leetcode #python
The last edge case is not the most confusing part, I find it pretty simple to understand.
What is confusing, is intuition to think about the min subarray.
same here, I was sitting there thinking about all possible ways to do this but I can't, until I find this hint about the min subarray. wish I could be smarter at the interview 🥲
Yeah, the total, globalMax and globalMin part confused me.
i like to imagine it like an obstacle,
if a maximum sum subarray exists in a circular formation, i.e. the left and right ends of the array, then the obstacle in the middle will be the minimum sum subarray, so taking the total - global min, we get the circular portion which is the globalmax
not worth learning it at all
explanation is ok. I feel the part I lack understanding the most is realizing the minimum sum subarray being used. Might be useful to explain why that could be a solution or why it works, rather than just telling us it's the answer
First of all, either the maximum sum subarray does not wrap around or it does. Suppose it does wrap around. Find the maximum subarray sum starting from i > 1 and ending at n - 1 inclusive (last item of the array). This will definitely be part of our solution. Now since we assumed the optimal solution includes wrapping around, we want to extend it from index 0 up to some index j > 0. Now suppose the minimum subarray was [k,l]. We want to show that i = l + 1 and j = k - 1. Because of minimality, we know that the sum of the surrounding elements 0, ..., k - 1 and l + 1, ..., n - 1 needs to be maximal. This sum must also be positive, otherwise we could have extended the minimum subarray. So we can conclude that the maximum circular subarray in this case will be [0, k-1] union [l+1, n-1].
Edit: We also need to prove that the subarray [0, k-1] union [l+1, n-1] sum is larger than any smaller circular subarray sum within that area. Call the [0, k-1] union [l+1, n-1] subarray sum S and the smaller subarray one s. Suppose s > S. Then that would mean that at least on one side of [k,l] there are contiguous elements whose sum is negative, and thus we could have extended the minimum subarray which is a contradiction since we assumed minimality.
A bit late but the way I thought of it is that minimum sum is an "obstacle" to the max sum, but since the array is circular, we can just walk around that obstacle. We can only walk around one obstacle though or else the subarray would no longer be contiguous, so that's why we're keeping track the biggest obstacle we need to avoid while compromising and tanking the smaller ones along the way (i.e for an array that contains the subarrays [-5,-10] and [-20], we can only walk around one of these obstacles, so we're keeping track of which one would hurt the sum the most (-20))
Amazing explanation as usual, thank you NeetCode !
However, I have to say that the intuition of "total - global_min will give us the potential answer of the circular case" is really hard to come up with...
Absolutely this! I tried for about an hour playing around with prefix sums, left + right pointers, dp, and other things
I felt the same thing, but Neetcode's solution has opened new pov.
@@Raymond-Wu
i copied the function i wrote for maximum subarray sum , instead of passing nums={5,-3,5} into the function i passed v={5,-3,5,5,-3,5} (flattening a circular array)
now the problem is it gives answer is 14 while actual answer is 10 and that is because if i am already including v[2] in my sub array i am not allowed to include v[5]
if length of nums is x (then v.size() is 2x)
if i am starting my subarray from index k
then i am only allowed to expand my sliding window upto index such that 2k+1 isnt included
or i can say they max length of my sliding window will be x at all times and this is how i prevented duplication
Awesome and easy to understand, thank you.
As always super explanation 🙂
You are awesome..👏i just love the way how you explains the every logic in an crystal clear format.. just a big fan of yourself.. need an autograph 😅shiiiiiiii🤪
Your consistency is impressive brother
Thanks for your work. Awesome videos, eloquent explanations, really helpful!
I chose to compare total to min. If they are same then return max. Seems OK, LeetCode accepted it as well. What do you think about this way of processing edge case of all negative numbers?
Rust code:
if total == min {
max
} else {
max.max(total - min)
}
Great explanation!
I love your explanations. Just one doubt how do you come up with those solutions, like the workaround for the circular array is total - globalMin. How did you figure that out ?
At some point in the starting of this video, you mentioned we want to be greedy for this problem, I don't think this is a greedy pattern. It more of look like DP approach where at each point or indexes you want to figure out what's the max sum I can achieve from this sub array. You are really breaking down the arrays to subarrays and trying to figure out the max sum can be achieve at particular index.
I don't quiet get the part,total - global min, how is that going to determine the max for circular array? how do i know if that included the circular case?
Hey , First you need to consider 2 cases :
1. MaxSumSubarray of the non-circular array.
2. MaxSumSubarray of the circular array.
3. Ans is the max of 1 and 2 .
First is straight forward apply - Kadanes
Second, is little tricky.
MaxSumSubarray of circular array = Sum of the entire array - (MinSumSubarray) .
How ? Imagine the minimum sum subarray is somewhere in the middle of your array. If the eliminate this from the total sum of the array we get the remaining sum.
To find MinSumSubarray : -(Kadane’s algorithm on the inverted array) . If some subarray is maximum in the inverted array then it is the minimum in the original array. Hope this helps. Took me a lot of time to understand the intuition. Hope this helps. :)
@@Kamalesh.2207 understood this well now
NeetCode has gotten so good at this now, that I have to slow down playback speed to in order to follow his logic.
Please make a video on Leetcode " 659. Split Array into Consecutive Subsequences ". I face difficulties to solve this.
good one
thanks
Why have another channel, Neetcode bro?
can someone explain what will happen with [-5,3,-5]? This will fail in that
I don't think the algorithm fails this test case. I threw this test case into leetCode, the algorithm returns 3. Do you expect a different result?
Before we hit the return statement, globMax = 3, globMin = -7, and total = -7.
Because the global max is greater than 0, we return the max between [3] and [-7 - (-7)] = 0.
So between choosing which is the max, 0 and 3, 3 gets selected.
If someone asked me this in an interview, id be screwed.
Can any one help and suggest me, how do you guys come up with this kind of approaches.
Yes I know kadane's algorithm, I've practiced with many other approaches and yet can't think of this kind of complex but simple intuition 😭😭. Frustrated 😩
try this approach bro
c3=0
for i in nums:
if(i0):
c=0
else:
ma=min(ma,c)
c1=0
ma1=nums[0]
for i in range(len(nums)):
c1+=nums[i]
if(c1
finally i saw a solution properly explaining logic after 5-6 videos
🙂
what you think about this solution
c3=0
for i in nums:
if(i0):
c=0
else:
ma=min(ma,c)
c1=0
ma1=nums[0]
for i in range(len(nums)):
c1+=nums[i]
if(c1
Great explanation! Wondering how this channel is different from your other channel www.youtube.com/@NeetCode 🤔
Neetcode are you Irish?.
guess what Sumit
no he's indian
tooooo fast
it's nothing to do with coding at all.. it's IQ and math test. How is it going to help people learning coding at all?
If the candidate pass this question, the only thing that can show is that this candidate spend a lot of time learning and this candidate is patient. Nothing else can prove this candidate is good coder or not.
Greedy algorithms 🥲... I wish I had studied computer science in College.
Fwiw most of this stuff I learned after college 😅