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#
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.
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.
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?
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?
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.
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.
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.
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
Remember that slicing nums[1:] is an O(n) operation, so it’s not actually saving any time over using max at the beginning. If we want to avoid that altogether we can just start res as float(‘-inf’) and curmax = curmin = 0
I think code readability is more important compared to the slight (if any) benefit in performance from doing this trick. Its still o(n), its not going to matter much
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 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.
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?
@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).
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.
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.
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]".
The intermediate values would overflow the range of integer. So for better to use a double for these variables, and cast it back to (int) before returning.
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.
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
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
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
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
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 TH-cam 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 :)
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?
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
a conceptually simpler approach: For any *r* boundary we want to include either the whole [0:r] if *curr* is positive, or (l:r] if not, where *l* is the index of the first negative element in nums. Rational: we want to include as many numbers as we can as long as we have an even number of negatives. So we calculate a *blob* that is the first negative product. Then at each step we compare the running *max* with either *curr* or *curr/blob* if *curr* is positive/negative respectfully. One last step is to reset *l* when we encounter a 0, because otherwise any sub-array that includes a 0 will produce 0. To do that we set blob back to original 1.
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
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.
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?
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)
Nope, that condition will mess up this test case. There should be no if condition. If we have the if condition, the result of your test case will be 1, not 0
@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
I have a question about negative. What if there are 3 negatives in array? Then I would have to choose center and left or right. But I don't think the min, max approach works for this. [2, -2, 4, -2, 6, -4, 5] I don't think it would work on this. Or any explanation for this.
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 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.
I feel like this is not a dynamic programming problem; it seems to me that it's not true that we look at the solutions of previous sub-problems and then use them directly to calculate the bigger sub-problem solution. Case in point: [4 5 6 -1 2 3] Let's say we came to the very last step, i.e. we have our min/max for the array [4 5 6 -1 2] and then we need to use that with 3. If this were the dynamic programming problem, you could say, well, I know the biggest sub-array product for [4 5 6 -1 2] and then I need to use it somehow with 3. But it wouldn't work. The biggest product for [4 5 6 -1 2] is 120, however, there's a gap between [4 5 6] and 3. It would be a mistake to just multiply 120 by 3. Instead, what we're doing is, we're kinda having this "rolling window" effect -- we are looking at the biggest/smallest sub-array STARTING from the right and going toward the left edge of the sub-array. That's why the code will give us "the current max" for [4 5 6 -1 2] as 2. And none of this would work had we not, at each step, memorized the biggest product we've found so far in `res`. So yeah, I hope my explained my rationale well enough - I don't think this is a usual dynamic programming task where one, at the last step, gets the final result by combining the previous sub-problems' results.
Thanks for the explanation! I think you can do curMax, curMin = max(n * curMax, n * curMin, n), min(n * curMax, n * curMin, n) if you dont want to have a temp value
Instead of resetting every time when you find 0 in the array. We can also use the element of array in comparison while deriving max and min at each level. class Solution { public int maxProduct(int[] nums) { int n = nums.length, maxProd = nums[0], minProd = nums[0], res = nums[0]; for(int i=1;i
I think the genius in the solution is not fully explained. The difficulty in this question is how to avoid segmenting the input or doing two-pointer type approaches to handle negative numbers and zeros. It is not immediately obvious that you can multiply the current max of previous values with the cell's value, n, and get a valid result, or that you can add 'n' to the max() / min() to skip zeros and negative numbers.
By what our known definition of Dynamic Programming is, is it technically correct to say this question IS dynamic programming (matter of factly), or is it more technically correct to say this question can be solving using a Dynamic Programming approach? I definitely see how this solution uses optimization on a problem by breaking it down into subproblems as you go through it, but most technical definitions I have seen love to only relate it in terms of memoization and recursion optimization. I am asking this mostly because I wonder if you can make a statement of fact like this in an interview, as I am currently just making sure my technical verbiage is sharper in terms of explanation.
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.
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;
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?
So the subproblem is actually the max/min of the current subarray that *includes* the last element. It got me confused for a bit, and I think you should always be clear on what subproblem we're solving in a DP problem.
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
Having the 3 arguments for cur_max/cur_min lets you avoid the if statement, as it just resets to the present num if previous calculations have been zero'd.
you may avoid using the tmp variable by: curMax, curMin = max(n * curMax, n * curMin, n), min(n * curMax, n * curMin, n) as in Python: a, b = b + 1, a + 1 -> will do the calculation simultaneously.
What if the array is [-4,-2,-3]. It doesn't work as it would be -8,8 and then -24, 24. But it will never be +24 multiplying these three. Am I missing sth? Edit: I understood it by researching a little more that -2 as the minimum that you got there is not by adding negative in-front of the maximum one, it's if you have to find the minimum and that would be by just taking -2. So for -4,-2,-3 would be -4, 8 --> -24, 12.
setting res to max(nums) adds extra computation that does nothing. curmin, curmax = 1, 1 res = float('-inf') for n in nums: tmp_n_times_max = n*curmax tmp_n_times_min = n*curmin curmax = max(tmp_n_times_max, tmp_n_times_min, n) curmin = min(tmp_n_times_max, tmp_n_times_min, n) res = max(res, curmax) return res
A[]= {-2,-9,0,0,3,4,0,0,11,-6} ans=18 ; But, After 3rd iteration, currMin=currMax=1; (or if u skip if loop then currMin=currMax=0) Desired result which is prod of first 2 elt, doesn't get destroyed as it is stored in maxProd variables💐
My solution simple and easy from functools import reduce from operator import mul a=[2,3,-2,4] b=[] for v in range(len(a)): for i in range(len(a[v:])): b.append(a[v:][:i+1]) print(max(b,key=lambda x: reduce(mul,x)))
You have to ask at each point in the array as you move through what the greatest and smallest product is or the value at the index itself. If the answer is that the value at the index is the most negative or the most positive we are removing from consideration the past values in our result subarray. Consider the following example. [2, -5, -2, -4, 3] at each index figure out the min and max subarray at that point index 0: min: 2 = [2] max: 2 = [2] (our only choice is 2 since we are at the beginning) index 1: min: -10 = [2,-5] max: -5 = [-5] (reset max) our choices ([2, -5], [-5]) index 2: min: -2 = [-2] (reset min) max: 20 = [2,-5,-2] our choices ([2,-5,-2], [-5,-2], [-2]) index 3: min: -80 = [2,-5,-2,-4] max: 8 = [-2,-4] our choices ([2,-5,-2,-4], [-2,-4], [-4]) index 4: min: -240 = [-2,-5,-2,-4,3] max: 24 = [-2,-4,3] our choices ([2,-5,-2,-4,3], [-2,-4,3], [3]) result 24 = [-2,-4,3]
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?
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!
"Do you at least agree with me, that if we want to find the max product subarray of the entire thing, it might be helpful for us to solve the sub-problem, which is the max product sub-array of just the full two elements first, and USE THAT to get the entire one. Okay, that makes sense". You added the last part so matter-of-factly but I didn't get at all why that makes sense. Why is multiplying the current number by the preceding two numbers somehow some magical trick to this?
say we have an array [1,2,3,4] running this code at the end of 4th iteration our current minimum product subarray would be 4 isnt this wrong? Shouldn't it be 1 in our case?
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!!
There is another easy solution. Run Kanane's product to get max from left and right, return max. public static int maxProductSubArray(int[] nums) { int max = nums[0]; int temp = 1; for(int i=0;i=0;i--) { temp *= nums[i]; max = Math.max(max,temp); if(temp==0) { temp=1; } } return max; }
![[Full] 4 ต่อ 4 Celebrity EP.920 | 3 พ.ย. 67 | one31](http://i.ytimg.com/vi/KwiW2M_kAg4/mqdefault.jpg)
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
thank you
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#
channel isn't underrated ngl
@@jude3926 Underrated I guess compared to those popular "programming" channels which are basically just "entertainment"
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
Yeah it's BS
Lmao I feel the same
@@rebornreaper194what is BS
@@beginner6667 the premise
@@beginner6667 bull sh*t
Hey, genuinely you're one of the best channels for this I've ever found. Thank you so much!
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.
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.
I hate random Jargon. "Kadane" doesn't tell me anything.
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?
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?
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.
most people that make these videos dont come up with the answers themselves so they cant explain how they got to it.
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.
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.
@@rodion988 Thanks, this helped me understand the logic better.
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
Remember that slicing nums[1:] is an O(n) operation, so it’s not actually saving any time over using max at the beginning. If we want to avoid that altogether we can just start res as float(‘-inf’) and curmax = curmin = 0
@@tearinupthec0astline True, but we could also just use a range-based for loop and start from index 1.
To add to this, only res needs to be initialized to the first array element, min and max can stay as 1
@@tearinupthec0astline we can use
For i in range(1,len(nums)):
num=nums[i]
Now this won't be a problem
I think code readability is more important compared to the slight (if any) benefit in performance from doing this trick. Its still o(n), its not going to matter much
Best explanation on youtube. Systematic and intuitive. Thanks for sharing!
that is clearest, coherent, and most understandable explanation I have ever met.
basically having n in max/min of (n*max, n*min, n) helped us sailing across the edge case of 0.
yup yup.
not only that it also helps in keeping the product of contiguous subarray (having 3 params in max and min function)
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
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.
dagg gai
@@noumaaaan they are considering the ith element too. Effectively you have max ending at ith element, min ending at ith element
@@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.
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?
Your channel is so underrated man. Thank you for doing this. I wish we had a professor like you in my college.
@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).
Thanks for explaining.
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.
i did
@@yagniktalaviya2146 wow
R u a competitive coder?
@@harsh9558 trying it out!
@@yagniktalaviya2146 amazing
@@yagniktalaviya2146 Good job man, I always believe whatever some random guy says on the internet.
for c++ coders ...
you can compare three values in max fn by using {}.
eg. maxVal= max({a, b, c});
Thanks!
I'm in awe, the way he explained it. Well done buddy. Explained a tough concept so easily.
me too
Honestly, the best explanations I have seen. Thank you so much, your doing an amazing job 👊🏽👊🏽👊🏽
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.
Additional point of order: min/max don't work on None, so initialize res as `float("-inf")` or -(math.inf)
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]".
The intermediate values would overflow the range of integer. So for better to use a double for these variables, and cast it back to (int) before returning.
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.
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
@NeetCode
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
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!
i found the procedure super complicated! Didn't understand why this method solves the problem.
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
output is still 0 with this code
The res = max(nums) initiation is extremely relevant - Should have a deeper focus on this if they ever remake the video...
CPP Solution:
int Solution::maxProduct(const vector &A)
{
int mx = 1, mn = 1;
int ans = INT_MIN;
for(auto& x : A)
{
if(x < 0) swap(mx, mn);
mx = max(mx*x, x);
mn = min(mn*x, x);
ans = max(ans, mx);
}
return ans;
}
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
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 TH-cam 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 :)
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?
Thanks man. Your channel deserves more subs.
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
this guy is leaps better than everyone else on youtube
a conceptually simpler approach:
For any *r* boundary we want to include either the whole [0:r] if *curr* is positive, or (l:r] if not, where *l* is the index of the first negative element in nums.
Rational: we want to include as many numbers as we can as long as we have an even number of negatives.
So we calculate a *blob* that is the first negative product. Then at each step we compare the running *max* with either *curr* or *curr/blob* if *curr* is positive/negative respectfully.
One last step is to reset *l* when we encounter a 0, because otherwise any sub-array that includes a 0 will produce 0. To do that we set blob back to original 1.
this is a crazy solution could not have thought of it
Hi, thank you for great explanation! Btw, time complexity of brute force is O(N^3). It can be optimized to O(N^2)
I was looking that someone would point this.
Dude, you are a GREAT teacher!! I wish I had you in my DSA class 🤣
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
Amazing channel found today, shoot up to 1 million soon!!
Nice explanation!
To work in leetcode submission:
curMax = max(curMax * n, n, curMin * n)
curMin = min(tmp, n, curMin * n)
Can you explain why this version works in leetcode but not what he wrote in the video? whats the difference
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.
Same, was searching for this
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.
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?
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
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
```
Great video...
Actually, we do need that if condition inside for-loop to handle the following kind of inputs:
nums = [-2,0,-1]
Nope, that condition will mess up this test case. There should be no if condition. If we have the if condition, the result of your test case will be 1, not 0
You made a very scary problem look easy. Thank you
now they have added new test cases which causes the overflow ,
THis is a gem of a channel; Nice work dude
@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
I have a question about negative. What if there are 3 negatives in array? Then I would have to choose center and left or right. But I don't think the min, max approach works for this.
[2, -2, 4, -2, 6, -4, 5] I don't think it would work on this. Or any explanation for this.
6:18 How is the minimum product of (-2 and -1 ) = -2 ? Shouldn't the maximum and minimum both be 2 ?
[-2] is also a subarray
@@joy79419 Thank you!
Very good explanation, we can initialize res with nums[0].
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 ?
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.
Anybody can help whether I am misunderstood something of the problem / solution being explained ?
@@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.
I feel like this is not a dynamic programming problem; it seems to me that it's not true that we look at the solutions of previous sub-problems and then use them directly to calculate the bigger sub-problem solution.
Case in point: [4 5 6 -1 2 3]
Let's say we came to the very last step, i.e. we have our min/max for the array [4 5 6 -1 2] and then we need to use that with 3.
If this were the dynamic programming problem, you could say, well, I know the biggest sub-array product for [4 5 6 -1 2] and then I need to use it somehow with 3. But it wouldn't work. The biggest product for [4 5 6 -1 2] is 120, however, there's a gap between [4 5 6] and 3. It would be a mistake to just multiply 120 by 3.
Instead, what we're doing is, we're kinda having this "rolling window" effect -- we are looking at the biggest/smallest sub-array STARTING from the right and going toward the left edge of the sub-array. That's why the code will give us "the current max" for [4 5 6 -1 2] as 2.
And none of this would work had we not, at each step, memorized the biggest product we've found so far in `res`.
So yeah, I hope my explained my rationale well enough - I don't think this is a usual dynamic programming task where one, at the last step, gets the final result by combining the previous sub-problems' results.
yep i agree. Optimal substructure doesnt apply here in all cases
Thanks for the explanation! I think you can do
curMax, curMin = max(n * curMax, n * curMin, n), min(n * curMax, n * curMin, n)
if you dont want to have a temp value
I just asked this same question XD
I wasn't sure if it would work that way or not
Instead of resetting every time when you find 0 in the array. We can also use the element of array in comparison while deriving max and min at each level.
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length, maxProd = nums[0], minProd = nums[0], res = nums[0];
for(int i=1;i
Very well explained. I loved it. Too good explanation. I have subscribed and liked. Keep making more videos. Awesome work really.
I think the genius in the solution is not fully explained.
The difficulty in this question is how to avoid segmenting the input or doing two-pointer type approaches to handle negative numbers and zeros.
It is not immediately obvious that you can multiply the current max of previous values with the cell's value, n, and get a valid result, or that you can add 'n' to the max() / min() to skip zeros and negative numbers.
By what our known definition of Dynamic Programming is, is it technically correct to say this question IS dynamic programming (matter of factly), or is it more technically correct to say this question can be solving using a Dynamic Programming approach? I definitely see how this solution uses optimization on a problem by breaking it down into subproblems as you go through it, but most technical definitions I have seen love to only relate it in terms of memoization and recursion optimization. I am asking this mostly because I wonder if you can make a statement of fact like this in an interview, as I am currently just making sure my technical verbiage is sharper in terms of explanation.
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.
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;
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?
just remove arr[0]=0
My main struggle with the problems in these technical interviews is finding solutions not requiring O(n squared).
So the subproblem is actually the max/min of the current subarray that *includes* the last element. It got me confused for a bit, and I think you should always be clear on what subproblem we're solving in a DP problem.
Yes exactly, otherwise we would have the result at curMax of the nth element, but that's not the case so we have to maintain a max result
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
Yeh the answer is 3, as the maximum is 3 overall
What about [0,0,-1]. It will give the wrong output .
Having the 3 arguments for cur_max/cur_min lets you avoid the if statement, as it just resets to the present num if previous calculations have been zero'd.
8:06
for example [-2, -1, -3]
[-2, -1] -> min=-2, max=2
[-2, -1, -3] -> can't get max = -2 x -3 = 6.
It's not contiguous
Very good explanation! But why do u initialize res to the max of nums?
you may avoid using the tmp variable by:
curMax, curMin = max(n * curMax, n * curMin, n), min(n * curMax, n * curMin, n)
as in Python: a, b = b + 1, a + 1 -> will do the calculation simultaneously.
Yes, but that does make it noisy to read
Do we have to store the curMin? I tried without it and it is working fine with all edge cases.
What if the array is [-4,-2,-3]. It doesn't work as it would be -8,8 and then -24, 24. But it will never be +24 multiplying these three. Am I missing sth?
Edit: I understood it by researching a little more that -2 as the minimum that you got there is not by adding negative in-front of the maximum one, it's if you have to find the minimum and that would be by just taking -2. So for -4,-2,-3 would be -4, 8 --> -24, 12.
so simple so elegant so beautiful
setting res to max(nums) adds extra computation that does nothing.
curmin, curmax = 1, 1
res = float('-inf')
for n in nums:
tmp_n_times_max = n*curmax
tmp_n_times_min = n*curmin
curmax = max(tmp_n_times_max, tmp_n_times_min, n)
curmin = min(tmp_n_times_max, tmp_n_times_min, n)
res = max(res, curmax)
return res
A[]= {-2,-9,0,0,3,4,0,0,11,-6} ans=18 ;
But,
After 3rd iteration, currMin=currMax=1; (or if u skip if loop then currMin=currMax=0)
Desired result which is prod of first 2 elt, doesn't get destroyed as it is stored in maxProd variables💐
My solution simple and easy
from functools import reduce
from operator import mul
a=[2,3,-2,4]
b=[]
for v in range(len(a)):
for i in range(len(a[v:])):
b.append(a[v:][:i+1])
print(max(b,key=lambda x: reduce(mul,x)))
awesome man , you have a soothing voice
You have to ask at each point in the array as you move through what the greatest and smallest product is or the value at the index itself. If the answer is that the value at the index is the most negative or the most positive we are removing from consideration the past values in our result subarray. Consider the following example.
[2, -5, -2, -4, 3]
at each index figure out the min and max subarray at that point
index 0: min: 2 = [2] max: 2 = [2] (our only choice is 2 since we are at the beginning)
index 1: min: -10 = [2,-5] max: -5 = [-5] (reset max) our choices ([2, -5], [-5])
index 2: min: -2 = [-2] (reset min) max: 20 = [2,-5,-2] our choices ([2,-5,-2], [-5,-2], [-2])
index 3: min: -80 = [2,-5,-2,-4] max: 8 = [-2,-4] our choices ([2,-5,-2,-4], [-2,-4], [-4])
index 4: min: -240 = [-2,-5,-2,-4,3] max: 24 = [-2,-4,3] our choices ([2,-5,-2,-4,3], [-2,-4,3], [3])
result 24 = [-2,-4,3]
i have been wrecking my head with this problem from yesterday , and your explanation is the best i could i ask for
Glad it was helpful!
Thank You So Much NeetCode Brother................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
watching your first video and subscribed.So clear and beautiful explanation❤❤
Shouldn't brute force be O(n^3)? We have n^2 sub arrays and calculating product for each is an O(n) operation.
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?
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!
I am not able to understand, why the initial value of curmin and curmax is 1, let's suppose the list is [0,0,0,0] , this should return 0 right?
"Do you at least agree with me, that if we want to find the max product subarray of the entire thing, it might be helpful for us to solve the sub-problem, which is the max product sub-array of just the full two elements first, and USE THAT to get the entire one. Okay, that makes sense". You added the last part so matter-of-factly but I didn't get at all why that makes sense. Why is multiplying the current number by the preceding two numbers somehow some magical trick to this?
You can avoid the three argument max, min and just use 2 arguments if you swap curMax and curMin when n < 0.
[3,-1,4] ---> Does this work for this one?
I'm not understanding how at 6:03, the min could be -2. Isn't it just 2?
beautiful explanation!
@NeetCode, another excellent video, in the video you captioned that the '0' check is completely unnecessary, can you pls elaborate how that would work
thanks man.. keep posting videos .its very helpful.
say we have an array [1,2,3,4] running this code at the end of 4th iteration our current minimum product subarray would be 4 isnt this wrong?
Shouldn't it be 1 in our case?
Hi , Can i know which ipad/tablet app are you using?
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!!
There is another easy solution. Run Kanane's product to get max from left and right, return max.
public static int maxProductSubArray(int[] nums) {
int max = nums[0];
int temp = 1;
for(int i=0;i=0;i--) {
temp *= nums[i];
max = Math.max(max,temp);
if(temp==0) {
temp=1;
}
}
return max;
}
Line 13: res = max(curMax, curMin, res)
this worked too
It is a very crisp solution. The challenge however is how to train your mind that solutions like these strike automatically.
I am using the same solution in java but I am ending up setting wrong value due to the size issue, any suggestion ?
6:03 i don't understand this part. why?
Hi NeetCode - Kudos to you Sir. Beautiful explanation.
The if-statement actually does break the solution, since it fails to detect when 0 itself is the max in the array