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.
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
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?
@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).
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.
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.
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.
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.
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?
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
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
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
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.
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.
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 UA-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 :)
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
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)
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.
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
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.
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?
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💐
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
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.
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?
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.
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 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.
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!
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]
"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?
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; }
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
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
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.
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
@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
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?
This is a great video and amazing explanation of this problem. However, the the about the zero case is wrong and introduces a bug in the code. Allowing zero does not seem to cause any issues (it works fine on all test cases on leet code without it), but with it it fails on [-2,0,-1] and returns -1, but in reality 0 is a valid answer in this case. 0 IS the max product of this array.
My solution in Python: import fileinput # Maximum subarray problem - Find the maximum sum in a continuous subarray. # Kandane's Algorithm def maxSum(nums): if len(nums) == 0: return nums[0] maxValue = minValue = globalMax = nums[0] for i in range(1, len(nums)): # Keep track of local minimum and maximum tempMax = maxValue maxValue = max(nums[i], nums[i]*maxValue, nums[i]*minValue) minValue = min(nums[i], nums[i]*tempMax, nums[i]*minValue) globalMax = max(globalMax, maxValue)
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.
java solution: public class Main { public static void main(String[] args) { int a[]={-2,3,-2,-4}; int current_sum=1; int max_sum=Integer.MIN_VALUE; for(int i=0;imax_sum){ max_sum=current_sum; } } if(current_sum
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?
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.
Awesome visualization and explanation! One thing I wanted to point out: the code as written doesn't handle the edge case of [-2, 0, -1]. Changing from "continue" to an if else block and add "res = max(res, 0)" handles it
🚀 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.
yes correct.. We can use dequeue data structure
Best explanation on youtube. Systematic and intuitive. Thanks for sharing!
that is clearest, coherent, and most understandable explanation I have ever met.
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
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?
Your channel is so underrated man. Thank you for doing this. I wish we had a professor like you in my college.
for c++ coders ...
you can compare three values in max fn by using {}.
eg. maxVal= max({a, b, c});
Thanks!
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)
@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.
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.
I'm in awe, the way he explained it. Well done buddy. Explained a tough concept so easily.
me too
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.
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.
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)
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?
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
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!
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...
i found the procedure super complicated! Didn't understand why this method solves the problem.
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
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
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;
}
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.
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.
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.
Thanks man. Your channel deserves more subs.
this is a crazy solution could not have thought of it
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 UA-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 :)
this guy is leaps better than everyone else on youtube
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
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
```
My main struggle with the problems in these technical interviews is finding solutions not requiring O(n squared).
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.
You made a very scary problem look easy. Thank you
THis is a gem of a channel; Nice work dude
Amazing channel found today, shoot up to 1 million soon!!
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
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
Very good explanation, we can initialize res with nums[0].
Very well explained. I loved it. Too good explanation. I have subscribed and liked. Keep making more videos. Awesome work really.
Dude, you are a GREAT teacher!! I wish I had you in my DSA class 🤣
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.
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
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
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💐
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
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
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?
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.
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.
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!
You can avoid the three argument max, min and just use 2 arguments if you swap curMax and curMin when n < 0.
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 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
now they have added new test cases which causes the overflow ,
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!
We don't have to store currMin because it is not being used again in the same iteration as currMax is used
It is a very crisp solution. The challenge however is how to train your mind that solutions like these strike automatically.
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]
"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?
so simple so elegant so beautiful
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;
}
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
Thank You So Much NeetCode Brother................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
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
Line 13: res = max(curMax, curMin, res)
this worked too
watching your first video and subscribed.So clear and beautiful explanation❤❤
It's interesting how currMax and currMin can get weird values during the for loop, but, at the end, the answer is right hahah
awesome man , you have a soothing voice
The if-statement actually does break the solution, since it fails to detect when 0 itself is the max in the array
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
@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
To avoid that n*curmax issue instead of using temp
curmin,curmax = min(n,n*curmin,n*curmax),max(n,n*curmin,n*curmax)
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!
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
And you could initialize the cur_Max and cur_Min with the first element instead of 1, BTW.
thanks man.. keep posting videos .its very helpful.
This is a great video and amazing explanation of this problem. However, the the about the zero case is wrong and introduces a bug in the code. Allowing zero does not seem to cause any issues (it works fine on all test cases on leet code without it), but with it it fails on [-2,0,-1] and returns -1, but in reality 0 is a valid answer in this case. 0 IS the max product of this array.
I ran the code on that test case and it does return 0.
I had the same issue. Look at what you are initializing your result to be. it should be max(nums) not 1 to start
@@NeetCode was this the reason you declared res with max(nums) rather INT_MIN
My solution in Python:
import fileinput
# Maximum subarray problem - Find the maximum sum in a continuous subarray.
# Kandane's Algorithm
def maxSum(nums):
if len(nums) == 0:
return nums[0]
maxValue = minValue = globalMax = nums[0]
for i in range(1, len(nums)):
# Keep track of local minimum and maximum
tempMax = maxValue
maxValue = max(nums[i], nums[i]*maxValue, nums[i]*minValue)
minValue = min(nums[i], nums[i]*tempMax, nums[i]*minValue)
globalMax = max(globalMax, maxValue)
return globalMax
# arr = [1,-3,2,1,-1]
# arr = [2,3,-2,4]
# arr = [-2,0,-1]
# arr = [-2,3,-4]
# arr = [3,2,1,2,3,-3,-9,8]
arr = [3,-2,-1,2]
print (maxSum(arr))
Hi NeetCode - Kudos to you Sir. Beautiful explanation.
Awesome explanation 🔥🔥
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.
Which universe you are coming from...!!!!! Really admired...🎉🎉
Update: `res = max(nums)` is actually unnecessary.
We can safely set `res = nums[0]`.
Not true for the implementation LeetCode uses, because of the if statement
java solution:
public class Main
{
public static void main(String[] args) {
int a[]={-2,3,-2,-4};
int current_sum=1;
int max_sum=Integer.MIN_VALUE;
for(int i=0;imax_sum){
max_sum=current_sum;
}
}
if(current_sum
This is one of those question where in order to come to the optimal solution during interview you should have had solved this before atleast once.
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 ?
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?
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.
Awesome visualization and explanation! One thing I wanted to point out: the code as written doesn't handle the edge case of [-2, 0, -1]. Changing from "continue" to an if else block and add "res = max(res, 0)" handles it
He initializes the result to max(nums). That should handle this test case.
simple and effective explanation :)
Thanku sir ... Your explanation is so simple to understand ...
Thanks! Happy it was helpful.
amazing explanation and oddly satisfying voice
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