Maximum Subarray Min-Product - Monotonic Increasing Stack - Leetcode 1856 - Python

[@NeetCode]

💡 SIMILAR PROBLEM: kzbin.info/www/bejne/sKmYhKpvZphjgpI

[@hfeng1995]

Leetcode has inflation issue. Used to be hard, now just medium :)

[@halahmilksheikh]

For anyone else wondering what the connection is between this problem and Largest Rectangle in Histogram. In the old problem, another way to think about it is "maximize the product of (the minimum value contained in a contiguous array) and (the length of the array)". We use the mono increasing stack to keep track of longest valid windows associated with each minimum value. Max MinProduct is an extension of Histogram so definitely understand Histo first if you're confused about MinProd.

[@yichenyao5927]

@@hfeng1995 for real! I feel like this is even trickier than the largest rectangle (which is Hard) by creating a prefix array. I got TLE for not creating that while the rest of the code following the exact structure of monotonic stack in largest rectangle (which I previously figured it out on my own)

[@halahmilksheikh]

These monotonic stack problems are more confusing than DP... at least with DP you can reason it out but here the logic is so confusing

[@danielsun716]

My question is during the 30 mins interview, how does we decide to use DP or monotonic stack?

[@tofahub]

That’s what I came to say

[@Alexander-zt9kz]

@@danielsun716really DP is for when you have a problem who can be solved by sub problems which are computed multiple times, so you cache them. Stack is used to emulate a callstack, reverse data, undo / check valid operations, or keeping items in monotonic order, either non decreasing or non increasing, sometimes with a twist. Harder monotonic stack questions are extremely difficult imo, much harder than DP or greedy questions.

[@ziomalZparafii]

I've solved dozen of leetcode and watched 3 times more of your solutions but this is the first one that I was unable to understand the problem and then also your explanation. Either it's too confused for me or I need to watch it again on some better day ;)

[@alexeysubbota]

You are not alone, me too!

[@Alexander-zt9kz]

Stack problems are literally the hardest pattern on LC, much much harder than DP.

[@dudeyouhavenoidea]

I didn't get the explanation at first but I eventually did

[@picturesqueedits3083]

watch strivers video largest histogram, he hasn't explained well

[@numberonep5404]

This one definitely earned its unofficial "Hard" tag omg xD Crystal clear explanation as usual, thank you!

[@mahesh_kok]

For people coming from largest rectangle in histogram below code explains the problem some modifications help avoid extra loops # this is my solution which is exactly the same as largest rectangle in histogram def maxSumMinProduct(nums) -> int: # add -1 to the end so that we can avoid extra while loop # for example when computing the last elemenet in nums # which is smallest and hence we will be computing the stack nums = nums + [-1] res = -1 stack = [] # adding 0 to the pre_comp_sum helps in calculating pre sum pre_comp_sum = [0] pre_comp_sum.extend(pre_comp_sum[-1] + n for n in nums) for index, ele in enumerate(nums): if stack and ele < stack[-1][1]: last_index = -1 while stack and stack[-1][1] >= ele: last_index, last_ele = stack.pop() new_res = last_ele * (pre_comp_sum[index] - pre_comp_sum[last_index]) res = max(res, new_res) stack.append((last_index, ele)) else: stack.append((index, ele)) return res

[@oswald3042]

Intuition in one line: Use monotonic increasing stack to get the sorting order of elements without actually sorting the array.

[@AymenDaoudi-u6h]

Intuition ? really ?!

[@nithinbosej]

Could have been better if explained with a bit bigger array like - [3, 1, 6, 4, 5, 2]. So some of the not-so-intuitive scenarios show up. But indeed a great explanation! Thanks!

[@brieflyfun]

It seems that having duplicated elements with the same value in stack is not useful. It is save to pop it out and put it back as newStart set to the original index. So change the while line condition stack[-1][1] > n to stack[-1][1] >= n will still work. So the stack would be strictly increasing.

[@RomanChurganov]

In a first place you should show on examples what we should include to sub-array as much numbers as we can to increase Min-Product, unless next number is smaller then smallest of sub-array. So smallest number acts like a baseline of a hill, and traversing with a stack while going down from hill it allows us to just keep track other side of the hill

[@mosaic34]

hey neetcode ! whenever i get stuck in a problem i always search you up first , you have an amazing and simple explanation which is always on point. i am trying to solve leetcode problem number 321 create maximum number and i couldnt find simple explanation to it anywhere on the internet , i am still stuck .....can you please make your next video solving that problem

[@NeetCode]

Thanks, yes I will solve that problem soon!

[@jdhp3696]

Thank you for the explanation. The last part of popping of the remaining stack is something that I did not think about.

[@DavidDLee]

Unlike most of your videos, the explanation here is not clear.

[@zhangxinhello]

Actually, you should point out: the key to solve this problem is find the firstLeftMinValue and RightMinValue for index i, that's why we use the stack

[@quentinau7507]

Watched it 5 times, finally understand the algorithm.

[@erdemtuna_me]

IMHO, 1-indexing prefix array usage creates a big difference (from coding perspective) in this problem in compared to 0-indexing...

[@shrimpo6416]

This question is very complicated, but perfect explanation and I finally understand it!

[@sarveshchavan4391]

Really appreciate your efforts for explaining ! Need more of such explanation for Hard problems

[@SRIDHARANBEE-jy9li]

Hii i just wanna thank you bro its literally amazing ❤️

[@SaurabhJeena-sh4gh]

easiest question of leetcode class Solution { public int maxSumMinProduct(int[] nums) { long max=Long.MIN_VALUE; Stack stack=new Stack(); long [] prefixSum=new long [nums.length]; int [] ns=new int [nums.length]; int [] ps=new int [nums.length]; long sum=0; for(int i=0;i=0;i--){ while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i]){ stack.pop(); } if(stack.isEmpty()){ ns[i]=nums.length; } else{ ns[i]=stack.peek(); } stack.push(i); } stack.clear(); for(int i=0;inums[i]){ stack.pop(); } if(stack.isEmpty()){ ps[i]=-1; } else{ ps[i]=stack.peek(); } stack.push(i); } for(int i=0;i

[@s_rox5042]

sliding window does not work here since we cannot decide to go left or right if the num[let_pos] == nums[right_pos]

[@abhisheksaraf2616]

this problem is similar to Largest Rectangle in Histogram there we are multiplying by index, here sum within range

[@sachinpaul2111]

This is the exact same pattern as that histogram rectangle problem

[@VerzapierZyGaming]

hey, what happens if the array is 1,2,3,1 we would still get a 2, that starts from idx 1 in the stack right? but the minimum is 1 at the idx 3?

[@NeetCode]

Before adding the 1, we would have to pop 3 and 2 from the stack. Once we pop those, we would compute if either 2 or 3 leads us to the max result.

[@VerzapierZyGaming]

@@NeetCode oh so we keep poping if its smaller than the peak of stack, got it thats where i had been mssinh great work!

[@haoyuwang3243]

I feel sad coz I still don't quite get it tho this is the clearest explanation on the planet of earth..This damn question..

[@amannegi8256]

amazing mate!

[@pranee31]

Neatly done

[@Sulerhy]

So confusing. Anyways thank you for your explain, it helps me step by step

[@liftandshiftdev3222]

i solved it using segment tree

[@SunilJamkatelTrue]

Isn't this a O(n^2) solution with the while nested loop?

[@vinayakgandhi5690]

It is O(N) Amortized. It looks like O(N^2) as we run a while loop in each iteration, but the total run time of the while loop over all n iteration is only N because we pop an element at most once.

[@vishnups]

Each element will be added to the stack exactly once. You can think of it as iterating over the input list once and over the elements of the stack once, making it two linear passes.

[@pramod3293]

What if the numbers can be negative?

[@avanishgvyas1992]

One feedback for the solution videos, not just this one but in general for all video solutions: It would help tremendously if you could show animation of the running algorithm to explain how it works.

[@yassineacherkouk]

this is not something that you can come up with alone.

[@naveen3192]

I can understand the steps in the problem and how it's solved but I don't quite get how these steps lead to generating all sub arrays. I don't get that connection. Can somebody help?

[@sodiqyusuff8019]

Looks like you haven't really understood the steps. So basically, you don't need to generate ALL sub arrays. Since you're multiplying all subarrays by the MIN val in the sub, that automatically means some sub arrays will be useless. Consider the array [1,2,5,1,0], and consider the element 2 at index 1. 2 belongs to sub arrays like [2,5], [2,5,1] and [2,5,1,0] but only [2,5] is useful to 2 because that's the only one for which 2 is the minimum. You will never multiply 2 by the sum of the rest so it's pointless to generate them. The popping of the stack when you encounter a smaller number helps to ensure this. I hope my explanation helps a little.

[@naveen3192]

@@sodiqyusuff8019 Hey, thanks for that. Rewatching the video now. I get why we don't need all sub-arrays. Thanks

[@jianhaoluo9491]

Solid!

[@piyushyadav9006]

I solved this using recursion .. Basically first I search for the min index and then I divided given array into two subarray to check whether they could give me the max without the min element. But in this method I've to sum all the subarrays again and again and thus time complexity is similar to that of QuickSort which is O(nlogn) Could there be any optimisation done.

[@chaoluncai4300]

Your way is actually Divide&Conquer, gj! could use a prefix sum to conquer the repetitive sum, but again has to compute the min of subarrays again and again... btw for breakin ties do you just skip all the candidates that's equals to the current minimum candidate?

[@jonaskhanwald566]

Mission successfully faile

[@jonaskhanwald566]

Need Combination sum IV - #377

[@shadowsw8020]

Badly explained

[@sparrow2068]

fr

[@Philgob]

this ain't no fucking medium