Maximum Product Subarray - Dynamic Programming - Leetcode 152

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/maximum-...
0:00 - Brute Force
2:00 - Drawing optimal Solution
10:00 - Coding solution
leetcode 152
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#product #subarray #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

[@abhinav4095]

thank you

[@edmonddantes587]

yeaaaah no chance I come up with this on the fly in an interview situation. Guess I'll have to memorise as many approaches as possible

[@rebornreaper194]

Yeah it's BS

[@xaenonch.8250]

Lmao I feel the same

[@beginner6667]

@@rebornreaper194what is BS

[@rebornreaper194]

@@beginner6667 the premise

[@shravani2922]

@@beginner6667 bull sh*t

[@CostaKazistov]

Highly underrated channel. You deserve 10x the number of subscribers. Clearest explanation style of Leetcode that I have come across yet - on par with Tech Dose and Back to Back SWE channels. Python is also a great choice for these videos, easy to understand, even though I only code in C#

[@jude3926]

channel isn't underrated ngl

[@jean4j_]

@@jude3926 Underrated I guess compared to those popular "programming" channels which are basically just "entertainment"

[@polyrain]

Hey, genuinely you're one of the best channels for this I've ever found. Thank you so much!

[@Sjejdbangdw]

Another way to think about it, perhaps more intuitive to some, is that we divide the array into segments that are separated by 0s (or consecutive 0s). Then, the total product of each segment is gonna be the largest for this segment unless its negative. In that case, we just divide it with the first negative product in the segment(to get a positive product) if possible.

[@robertsedgewick1266]

Best explanation on youtube. Systematic and intuitive. Thanks for sharing!

[@abbyjon461]

Your channel is so underrated man. Thank you for doing this. I wish we had a professor like you in my college.

[@Zero-bg2vr]

I'm in awe, the way he explained it. Well done buddy. Explained a tough concept so easily.

[@THEAVISTER]

Honestly, the best explanations I have seen. Thank you so much, your doing an amazing job 👊🏽👊🏽👊🏽

[@josuegialis3]

I am so happy and satisfied with the quality of your solutions and thorough explanations. Thank you so much and please keep up the good work!

[@andrewmelnikov3102]

that is clearest, coherent, and most understandable explanation I have ever met.

[@superchetube]

Hard to imagine a company ask this question during the interview. I don't know if anyone can come up with the solution in a few mins if never meet this problem before.

[@yagniktalaviya2146]

i did

[@harsh9558]

@@yagniktalaviya2146 wow R u a competitive coder?

[@yagniktalaviya2146]

@@harsh9558 trying it out!

[@vallabhchugh2075]

@@yagniktalaviya2146 amazing

[@abhijit-sarkar]

@@yagniktalaviya2146 Good job man, I always believe whatever some random guy says on the internet.

[@sliverofshadows475]

Great video. The catch of the question seems to be in knowing that we need to also track the minimum _in addition_ to the maximum, but I have some trouble understanding how we could manage to figure that out. Of course, once the answer is given, the whole solution makes sense, but when I was trying to do this question on my own, the thought of tracking the minimum never even occurred to me. Any tips on how to go about warping your thought process to think about that as well?

[@protyaybanerjee5051]

Haha! Same question, but the answer is invariably "Solve more problems" . I think that it's pretty tough to come up with this solution in an interview setting, unless you have practised similar problems.

[@Majitsu]

most people that make these videos dont come up with the answers themselves so they cant explain how they got to it.

[@rodion988]

You get to this idea when you think about edge cases and realize that you don't know how many negative values there are. 0 : You have to reset your current product at each 0 and treat the rest as a new array. Negative value: makes your prior results negative. Will make the sum positive only if after it another negative value is encountered and there was no 0 in-between. So after encountering a negative value you always have 2 paths you can follow and you don't know which one will turn out to be bigger. But the negative value multiplied with positive numbers will become only smaller... Which is good: the negative value grows but in a different direction. So we have to take min() of it.. it allows the current negative result to grow into negative direction as max() allows current positive result to grow into positive direction. The next time we encounter second negative and multiply the current negative (min) result with it, it will turn out to be a bigger positive value than what we had in the current positive result variable.

[@alexcuenca]

Many of these problems have tricks that it's very unlikely one can figure out. But don't worry, it doesn't mean much really. I'd bet this is the case for everyone given a significant amount of problems. You just have to check the solutions in these problems a lot of the times. Everybody does it. Whoever says they don't, be suspicious lol.

[@merrygamer236]

@@rodion988 Thanks, this helped me understand the logic better.

[@DanhWasHere]

I love that you didn't mention Kadane's Algorithm so we don't get hung up on the terminology of "Max Product Subarray" => apply Kadane's and instead just understand the logic. E.g. A lot of YoutTube videos are titled how to apply Kadane's Algorithm instead of the type of problem it is used for, which is the more important information.

[@TheDSasterX]

I hate random Jargon. "Kadane" doesn't tell me anything.

[@leeroymlg4692]

it's probably best that these problems aren't taught to use some algorithm named after a person. Because how many people actually have every single algorithm someone else came up with memorized?

[@empowercode]

Hey! I just found your channel and subscribed, love what you're doing! Particularly, I like how clear and detailed your explanations are as well as the depth of knowledge you have surrounding the topic! Since I run a tech education channel as well, I love to see fellow Content Creators sharing, educating, and inspiring a large global audience. I wish you the best of luck on your KZbin Journey, can't wait to see you succeed! Your content really stands out and you've obviously put so much thought into your videos! Cheers, happy holidays, and keep up the great work :)

[@sasirekhamsvl9504]

Very well explained. I loved it. Too good explanation. I have subscribed and liked. Keep making more videos. Awesome work really.

[@saibharadwajvedula6793]

basically having n in max/min of (n*max, n*min, n) helped us sailing across the edge case of 0.

[@ChrisCox-wv7oo]

yup yup.

[@geekydanish5990]

not only that it also helps in keeping the product of contiguous subarray (having 3 params in max and min function)

[@goodtoseeya1543]

Thanks man. Your channel deserves more subs.

[@visa2learn]

Amazing video, I like the way you explain things. Kudos. Just want to point out that res = max(nums) at the beginning is not needed if you remove the if (n ==0) check. max function would need to iterate the entire array to find out the max. If the array is huge, this will take significant amount of time.

[@The9TKitsune]

Additional point of order: min/max don't work on None, so initialize res as `float("-inf")` or -(math.inf)

[@smrutiranjansahoo9161]

Thank you! I just want to make a small suggestion. We can initialize the result with the first element of the input array. It will simplify the solution further.

[@vimalslab3398]

for c++ coders ... you can compare three values in max fn by using {}. eg. maxVal= max({a, b, c});

[@khangpiano549]

Thanks!

[@mrigankanath7337]

THis is a gem of a channel; Nice work dude

[@dorondavid4698]

For your code, in your optimal solution section, you use an example of [-1, -2, -3], and then say the max is 2 and the min is -2 I don't think your algorithm will work if the array was [-2, -1, -3]. The min and max would be the same, but it wouldn't be a CONTIGUOUS subarray answer then. Please correct me if I'm wrong! Edit: Actually the code makes sense when I look at it because you take the min of THREE items. From the description part it sounded like you were just taking the min/max and that's it

[@noumaaaan]

I swear i was just thinking about this and hoping someone else noticed. Can you please explain how it works, since it's not contigious.

[@mynk_rjpt]

dagg gai

[@tarunpahuja3443]

@@noumaaaan they are considering the ith element too. Effectively you have max ending at ith element, min ending at ith element

[@bestmovies36]

​@@noumaaaan I was in the same boat during explanation time but my doubt got clarified after coding. Because here we are considering min and max products till zero value appears.

[@kamsalad]

Still don't really understand this let's say you have an array: [1, 2, 3, 0, 1, 2] The maximum product subarray is 6 If you add one more number you would have something like: [1, 2, 3, 0, 1, 2] [3] Here, the answer is still 6, but shouldn't it be 3*6 = 18, according to the video?

[@sharad3877]

watching your first video and subscribed.So clear and beautiful explanation❤❤

[@camoenv3272]

A fun trick I like to use is to initialize curMin, curMax, and result to the first number of the array, then iterate over all elements of the array except for the first. Then we don't need to run a max operation to determine the initial result. Also, if you do the new curMax and curMin calculations on a single line, you can avoid using a tmp var. (The entirety of the right side of the equals sign is evaluated before the newly computed values are assigned to the vars def maxProduct(self, nums: List[int]) -> int: curmax = curmin = res = nums[0] for num in nums[1:]: # remember to include num, so we can reset when a 0 is encountered curmax, curmin = max(curmax * num, curmin * num, num), min(curmax * num, curmin * num, num) res = max(res, curmax) return res

[@tuanp01]

So far, your series has been great thank you. Please elaborate more on the section “drawing the optimal solution”. If the array was [-2,-1,-3,4] the max product should be 12. However, following your min, max strategy it computes to 24

[@tuanp01]

@NeetCode

[@yadwindersingh806]

for n = -2, we get max = -2, min = -2, maximum product = -2 for n = -1, max = -2, min = -2, we get max = 2, min = -1, maximum product = 2 for n = -3, max = 2, min = -1, we get max = 3, min = -6, maximum product = 3 for n = 4, max = 3, min = -6, we get max = 12, min = -24 maximum product = 12

[@im_another_you]

Hi NeetCode - Kudos to you Sir. Beautiful explanation.

[@fahim0404150]

The explanation is very good. However the test case have changed over the past 3 year. If i run this code in (c++) I get a "runtime error: signed integer overflow" for the input of "nums = [0,10,10,10,10,10,10,10,10,10,-10,10,10,10,10,10,10,10,10,10,0]".

[@satya1067]

Awesome explanation 🔥🔥

[@abdosoliman]

I went with a slightly different approach I divided it into a map of ranges and their product. So basically I start at a value keep multiplying until I see a zero then I use the start,end indecies as map keys and the value is the product. After constructing the map then it's simple you make a for loop that keeps dividing until it hits the first negative number. Another for loop keeps dividing from the back till hits the last negative or the first negative from the back. We compare and update the max_product. My solution is practically the a single pass but I would prefer your solution because it's less code and easier to understand.

[@chiranjeevipippalla]

You made a very scary problem look easy. Thank you

[@anikethdeshpande8336]

simple and effective explanation :)

[@arpitcts]

For values [-2,0] this code returns -2. where as the output should have been 0. so I have made one slight change. I kept the flag to indicate if we found zero. and at the end, if (flag) max(res,0) else return res

[@HanSmellsGood]

output is still 0 with this code

[@ritwikpm]

The res = max(nums) initiation is extremely relevant - Should have a deeper focus on this if they ever remake the video...

[@vaibhavpatil1152]

thanks man.. keep posting videos .its very helpful.

[@matthewfourie3666]

Awesome video, explained it so well! thanks man

[@NeetCode]

Thanks!

[@HarveySpecterYT]

Thanx for this great explanation. :)

[@xingdi986]

since minimal/maximal number times the negative/positive number could both achieve the maximum product, you need to note down both minimal and maximal. Do I understand correctly?

[@hwang1607]

this is a crazy solution could not have thought of it

[@rajdeepchakraborty7961]

great explanation!!

[@ranadebnath5421]

Thanku sir ... Your explanation is so simple to understand ...

[@NeetCode]

Thanks! Happy it was helpful.

[@alviahmed7388]

@NeetCode, I am really bad at identifying patterns like this. What can I do to get better at it? You are good at approaching problems from different angles which is stuggle with

[@aritralahiri8321]

Very neatly done.

[@lucaswang8457]

As always, it's so neat!

[@AliBazilov]

Hi, thank you for great explanation! Btw, time complexity of brute force is O(N^3). It can be optimized to O(N^2)

[@TheMadRunner00]

I was looking that someone would point this.

[@aseemsameer7281]

Mostly the questions require returning a subarray that contains maximum product. Here, with all the cases considered by you, we need a storage of numbers in the array and their product till nth position, and continuing from those to add new elements. For such purposes, dynamic programming becomes more complex. Is there any simpler solution to this?

[@supreethvasisht2451]

i found the procedure super complicated! Didn't understand why this method solves the problem.

[@mostinho7]

6:20 this is same as kadane’s algorithm for maximum subarray, where we keep track of max subarray ending at ith index. For this problem since two negatives multiplied together give a positive, we need to keep track of the min subarray ending at ith index AND max subarray ending at ith index. Then for i+1 position, if it’s a negative value, then the max product subarray ending at i+1 position is that value * min subarray ending at ith position (if it’s negative value) Dealing with 0s as elements, the zero resets our min and max subarray ending at 0 element’s index. So both min and max become 1 after encountering 0

[@optimistic_dipak8632]

Great video... Actually, we do need that if condition inside for-loop to handle the following kind of inputs: nums = [-2,0,-1]

[@vivivi5678]

When i tried this solution in java, i got an error for one of the testcases due to integer range issue. I changed it to double and it worked.

[@vroomerlifts]

Same, was searching for this

[@tejeshvaish17]

awesome man , you have a soothing voice

[@salonidabgar1174]

We'll also have to store the value of currMin till the previous iteration in a temporary variable as we did for storing currMax. This was the only problem with the code. Otherwise, great explanation!

[@AbhishekKumar-ym1pz]

We don't have to store currMin because it is not being used again in the same iteration as currMax is used

[@lukenothere1252]

Man, I love your explanation

[@shashankgarg7476]

Amazing channel found today, shoot up to 1 million soon!!

[@patrickadjei9676]

At first I was like... it might still do 1*2*4 = 8 although the answer is 4. But after printing it out, I was like wow... nice work.

[@Ezio-lp8iq]

Please share your google interview experience, also did u do more than those 150 problems, and if you could share...awesome series!

[@user-ul1rn4iz4v]

Very good explanation, we can initialize res with nums[0].

[@crossvalidation1040]

Nice explanation! To work in leetcode submission: curMax = max(curMax * n, n, curMin * n) curMin = min(tmp, n, curMin * n)

[@mastermax7777]

Can you explain why this version works in leetcode but not what he wrote in the video? whats the difference

[@ravijha4965]

if input is with only [0] and without that assignment line of res = max(nums), how can we save this time here removing this line ?

[@gauravthehero]

@NeetCode, another excellent video, in the video you captioned that the '0' check is completely unnecessary, can you pls elaborate how that would work

[@ikthedarchowdhury8947]

Do we have to store the curMin? I tried without it and it is working fine with all edge cases.

[@stith_pragya]

Thank You So Much NeetCode Brother................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@joshuabump6147]

My main struggle with the problems in these technical interviews is finding solutions not requiring O(n squared).

[@pakkunhatake]

Solid video, just a small correction. For the DP part, we are actually finding the min/max of the subarray ending in the ith index. So once we reach the end, it's not necessarily that the last element has to be included in this max subarray. But by the end we would have already encountered the max subarray as we were processing and saved it already in our return variable. Another way to think about is that if we had two arrays dpMin and dpMax, both of length N, which represent the min and max of subarray ending at ith index. We use both of these in our computation. And then at the end of our algorithm we can return max(dpMax). The reason we can do away with these arrays is that we only look back one index, i.e., we only look at dpMin[i-1] and dpMax[i-1], so removing the arrays is an optimization in and of itself

[@insaneclutchesyt948]

we dont need to check for zero right because we are taking min, max of three elements in which the nums[i] is also there so it will take the nums[i] , and the currmin currmax will not become 0 for the remaining array ! correct me if im wrong

[@roxanamoghbel9147]

Great explanation

[@fatty-it-man]

I have a simpler solution: 1) check where the zeros are. zeros split the array into segments. each segment is treated the same. 2) for each segment, check how many negative numbers in each segment. 2.1) if there is an even number (i.e. 0, 2 4 ...) of negative numbers -> the max product is the product of the whole segment. 2.2) if there is an odd number of negative numbers -> choose the max between products of the "left" part of the segment and the "right" part. example: [1,2,3,-1,4,5,6,-2,7,8,9,-3,10,11,12 ] - left part: part of the segment that contains numbers from the left side to the last negative number(not including), [1...9] - right part: part of the segment that contains numbers from the first positive number (including) which resides after the first negative, to the last number of the segment, [4...12]

[@sagnikmukherjee5108]

Brilliant explanation.

[@RandomShowerThoughts]

this guy is leaps better than everyone else on youtube

[@arnobpl]

Great explanation! We can refactor the code for even better readability: ``` def maxProduct(self, nums: List[int]) -> int: product = nums[0] maxx, minn = product, product for x in nums[1:]: newMaxx = max(x, maxx*x, minn*x) newMinn = min(x, maxx*x, minn*x) maxx = newMaxx minn = newMinn product = max(product, maxx) return product ```

[@vasudhajha9115]

Thank you for the solution! You've made it very intuitive! But how do you tackle the case where all the elements in an array are zero?

[@arkamukherjee457]

It's handled, max(0,0,0) is 0.

[@alltechsimplified2134]

it will not work for [-2,-1,-3] answer it is giving is correct but the answer is considered of [-2.-3] which are not contiguous sub array means you are violating the constraint that is much important

[@namanvohra8262]

Very good explanation! But why do u initialize res to the max of nums?

[@andrepinto7895]

You can avoid the three argument max, min and just use 2 arguments if you swap curMax and curMin when n < 0.

[@srr1424]

Thank you for the Nice solution.

[@ujjawalpanchal]

@NeetCode, you don't need to introduce 1s in the zero condition. It works even without that. Because you are taking a `max(num, curr_max * num, curr_min * num)` so if curr_max * num = 0, max will be num incase of +ve num. Also, for -ve num, you are taking min(num, curr_max * num, curr_min * num)` so for -ve num, if curr_max * num == 0 and curr_min * num == 0, curr_min will be set to num (since num < 0).

[@vdyb745]

Brill explanation !

[@kahlilkahlil9172]

How does the usage of min will work as this is a contigous subarray ? for example if the array is [-2, -1, -3] then the max of sub [-2, -1] is 2 while the min is -2, if we try to get -3 * -2 this is wrong, because it become a non-contigous array.

[@kahlilkahlil9172]

Anybody can help whether I am misunderstood something of the problem / solution being explained ?

[@VignetteQ]

@@kahlilkahlil9172 Late response but the reason that doesn't happen is in the line that sets curMin = min(..., curMin * n, ...). In your example curMin would have the value of -1 when n = -3, not -2; curMin will always be updated with each n. Your example would occur if the min() calculation had not curMin * n, but just curMin.

[@hoyinli7462]

great explanation

[@nithinchitra1570]

thanks for sharing knowledge 😊😊

[@yidatong443]

How about -2, -1, -3? For (-2, -1) max-> 2, min->-2. Then for (-2, -1, -3) max->-3*-2 = 6, min ->-3*2=-6. But (-2, -1, -3) max->[-1, -3] = 3 min->[-2, -1, -3]=-6

[@amitmahato4876]

Yeh the answer is 3, as the maximum is 3 overall

[@k12561]

anyone know why the if statement in the final solution is unnecessary? is it because line 13 would retain the original res value which is the previous max?

[@_bancini_6355]

It seems to work even if we initiate res as equal to nums[0], getting rid of unnecessary max(nums)

[@jasonuranta7653]

Hi! Can someone explain why you don't need an if statement for the 0 case in order to set the curMax and curMin to 1s? To my understanding if the next n is 0 then curMax = max(n * curMax, n * curMin, n) would just end up as curMax = max(0 * curMax, 0 * curMin, 0) which would be curMax = max(0, 0, 0), getting you curMax = 0. Vice Versa for curMin too. So it seems like that if statement for the 0 case is necessary to me. Thank you!

[@visiedo72]

Sorry, but this solution wouldn’t work for input arrays where all values are negative or 0, would it? Eg for [-2, 0, -1] it would yield -1 as the result, right?

[@chanakyakenguva3795]

No, as he has taken res = max(nums) in line no 3, the res would be set to 0 when all values are negative or 0

[@qwerty6-6]

6:18 How is the minimum product of (-2 and -1 ) = -2 ? Shouldn't the maximum and minimum both be 2 ?

[@joy79419]

[-2] is also a subarray

[@qqqqoeewqwer]

@@joy79419 Thank you!

[@nevingeorge989]

is the max the max product sequence in the sub array? in the array [1,-2] at -2 the max is calculated as -2 but shouldnt it be 1

[@omerapl3511]

Can anyone elaborate when it's usefult to save min and max of an array? I'm tring to implement this idea to a several different questions and really want to put my finger on when this technique is useful. Thanks!!

[@mandy1339]

I could think of a non dynamic programming solution in about 1 hr. (Do running cumulative multiplication from left and one from right and take the max) However I struggled to see the dynamic programming approach.

[@shrn]

Great idea with the running cumilative multiplication from left and right

[@jingrrrl5765]

Thanks for the video. I don't think it's necessary to check if n==0, because line 11 and 12 have n in max and min function, which did the job already

[@AsliArtistVlogs]

You sound like Clement from AlgoExpert lol

[@naveen9102]

i have been wrecking my head with this problem from yesterday , and your explanation is the best i could i ask for

[@NeetCode]

Glad it was helpful!

[@MrChinmaykulkarni]

best explanation

[@__________________________6910]

Nice one !

[@vanillatrivedi]

For the input array {-2,0,-1} , I was getting the result as -1 instead of 0. i believe when we 're resetting the min/max value as 1 we need to reset the maxsub to it;s default.

[@ir2001]

Solution: Check whether the input array contains a zero (for example, use a flag variable and update it before "continue" when you encounter a 0). Then, if "res" comes out to be a negative integer when it has been found that the input array contains a 0, the maximum product would indeed be zero (the edge case that you rightly pointed out); otherwise, "res" is correct. if (res < 0 and zeroPresent) { return 0; } return res;

[@MrHunty]

What I did that helped this issue, was inside the if statement, I added a clause that "result = Math.max(result, 0)" which checks to see if 0 is bigger than what is the current max. It passed all of leetcodes tests, so I'm assuming it's okay?

[@pankajupreti8967]

just remove arr[0]=0

[@harshit4190]

how do we figure out start and end index in this question?

[@AmanKumarSharma-de7ft]

How can you remove the if (n==0) condition and this still runs??

[@lemons.3018]

now they have added new test cases which causes the overflow ,

[@anshab16]

so simple so elegant so beautiful

[@adhoc3018]

I think that line 3 can also only be res = nums[0], assuming that nums is never empty.

[@anilpank]

It is a very crisp solution. The challenge however is how to train your mind that solutions like these strike automatically.