Maximum Sum Circular Subarray - Leetcode 918

Maximum Sum Circular Subarray - Leetcode 918 - Python

Рет қаралды 35,206

Күн бұрын

Пікірлер: 51

@AymenDaoudi-u6h Жыл бұрын

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.

@yichenyao5927 Жыл бұрын

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 🥲

@CST1992 5 ай бұрын

Yeah, the total, globalMax and globalMin part confused me.

@natisaver 3 ай бұрын

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

@jasonwang3690 2 ай бұрын

not worth learning it at all

@hamzasayyid8152 Жыл бұрын

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

@ZeonLP Жыл бұрын

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.

@bezu6784 Жыл бұрын

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

@laumatthew71 Жыл бұрын

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

@Raymond-Wu Жыл бұрын

Absolutely this! I tried for about an hour playing around with prefix sums, left + right pointers, dp, and other things

@sionkim5504 Жыл бұрын

I felt the same thing, but Neetcode's solution has opened new pov.

@ary_21 Жыл бұрын

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

@vijethkashyap151 Ай бұрын

@@ary_21i had the same approach, but this gives TLE for me. I flattened the array and then called Kadane’s algorithm for each window of len(nums) (original length) and maintained max result for each window. But this gave TLE

@SriJahnaviChinthalapudi-wz8us 2 ай бұрын

Very clear explanation, such a complicated problem is explained in a simple manner

@sunilpanchal1498 Жыл бұрын

As always super explanation 🙂

@bgovindnaren7405 23 күн бұрын

Beautiful explanation bro! thanks

@LokeshPandey-j6k 11 ай бұрын

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.

@nmprecious Ай бұрын

This is greedy because at each step, you're optimizing for the best solution possible without caring about the next best pattern. Finding the current max and updating the max is a greedy behavior, and so is finding the current min then updating the global min.

@JuliaC-mz8qy 3 ай бұрын

If someone asked me this in an interview, id be screwed.

@anantajitraja1035 4 күн бұрын

Hi, I somewhat understand the final conditional statement at 16:12 - but how would you spot that edge case and know for sure that it's the only important edge case here if, say, you've never seen the problem before?

@jessanraj9086 Жыл бұрын

Your consistency is impressive brother

@CostaKazistov Жыл бұрын

NeetCode has gotten so good at this now, that I have to slow down playback speed to in order to follow his logic.

@GreenChiou Жыл бұрын

Awesome and easy to understand, thank you.

@himanshisharma7116 Жыл бұрын

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🤪

@robr4501 Жыл бұрын

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?

@Kamalesh.2207 3 ай бұрын

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

@anusree8707 3 ай бұрын

@@Kamalesh.2207 understood this well now

@piyusharyaprakash4365 Жыл бұрын

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 ?

@Kayander1 Жыл бұрын

Great explanation!

@shubhampatel7870 Ай бұрын

How do I come up with this thought in an interview that max circular subarray sum is the complement of the min subarray sum 🙂

@ouchlock Жыл бұрын

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) }

@loganjame 10 ай бұрын

can someone explain what will happen with [-5,3,-5]? This will fail in that

@JuliaC-mz8qy 3 ай бұрын

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.

@saikatrakshit3286 Жыл бұрын

Please make a video on Leetcode " 659. Split Array into Consecutive Subsequences ". I face difficulties to solve this.

@pushkarchaubey8300 7 ай бұрын

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

@LiveWithAdarsh 4 ай бұрын

good one

@eddiej204 Жыл бұрын

Why have another channel, Neetcode bro?

@mohit8299 6 ай бұрын

thanks

@manishdangi5491 Жыл бұрын

finally i saw a solution properly explaining logic after 5-6 videos 🙂

@lichuntak5143 8 күн бұрын

How is 3 -2 1 the max subararry sum

@MIRAZIB Жыл бұрын

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 😩

@pushkarchaubey8300 7 ай бұрын

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

@jasonwang3690 2 ай бұрын

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?

@jasonwang3690 2 ай бұрын

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.