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

0:00 - Read the problem
2:50 - Intuition
10:45 - Drawing Explanation
18:18 - Coding Explanation

leetcode 1856

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

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

[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

[numberonep]

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

[oswald]

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

[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]
+ 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

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

[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!

[mosaic]

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 you please make your next video solving that problem

[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

[jdhp]

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

[s_rox]

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

[erdemtuna_me]

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

[DavidDLee]

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

[sarveshchavan]

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

[shrimpo]

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

[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?

[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

[abhisheksaraf]

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

[quentinau]

Watched it 5 times, finally understand the algorithm.

[SRIDHARANBEE-jyli]

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