Just a small change in the code for those who are wondering why 191th test case is not passing on leetcode, just change the data type of ans, pre and suff to double so as to prevent overflow in the intermediate steps. It has much bigger range than long and long long. Btw great explaination striver!!
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.....
bro no need any more examples you were the best in explaining this question with the most examples the cases... Really understood the concept very well. Thank you for the video...
This approach is awesome! I've seen others teaching the same old Kadane approach, but this observation-based method is a real gem. Keep up the great work and keep sharing your insights!
Brilliant! this is actually much more intuitive as I was also thinking of applying prefix and suffix in it, just couldn't react to the final answer. Thanks.
This will pass all testcases in leetcode class Solution { public: int maxProduct(vector& nums) { long long pre=1,suf=1; long long maxi=INT_MIN; for(int i=0;i
I do not know who has observed the optimal approach but whoever the guy was, it was brilliant Thanks for your explanation Striver Understood it very well And waiting for your Binary Search series...
It should work if at the start you intitialize the max at min_int or min infinity in python. This way 0 will get picked. No need to change the max() part.
Java code for 191th test case:- class Solution { public int maxProduct(int[] nums) { int n=nums.length; if(n==0)return 0; double ans= Integer.MIN_VALUE; double pref=1, suf=1; for(int i=0; i
im so happy that i did this prblm both brute and optimal by myself....only difference in my code was i did traversal two times to calc prefix and suffix😅. BTW THANKS STRIVER YOU ARE GREAT🙇
This solution works well except one edge case where we have a 0 in the array and even number of negative elements. In that case there is a possibility that 0 is our final answer if all other multiplications are negative. A simple tweak can help us solve this just maintain a zeroflag and before returning the answer just check if the answer is negative and the zeroFlag is set in that case we will simply return zero as our answer since we have a zero element in the array and the maximum subarray product excluding zero is negative.
But that's already covered. Let's take an example as per your expl. : -4 0 -5 , here 0 exists and even negative elements In the first iteration pref=-4 suff = -5 , max=-5 second : pref=0 , suff=0 , max = 0 third : pref=-5 , suff=-4 , max=0 So we need not take any such flag or maybe you can specify any test case where your approach will work.!
if you're getting error due to testcases with starting or ending zeroes, then this solution should work: #include #include using namespace std; int subarrayWithMaxProduct(vector &arr){ int n=arr.size(); int pre=1, suff=1,maxprod=INT_MIN,prezero=0,suffzero=0; for(int i=0;i
One test case fails in leetcode using this solution. Below is the corrected code. Take prefix and suffix as double. class Solution { public int maxProduct(int[] nums) { int max = Integer.MIN_VALUE;; double prefix = 1; double suffix = 1; for(int i=0; i
awesome teaching and please teach every problem how to identify the pattern which algo we need to used.. and try to explain all the approaches. by the way your videos are great you will deserve 1m soon.
I solved this problem using a extended version of kadane's algorithm: class Solution { public int maxProduct(int[] nums) { int currmin=1,currmax=1,max=nums[0]; for(int n:nums) { int temp=currmax*n; currmax=Math.max(currmax*n,Math.max(currmin*n,n)); currmin=Math.min(temp,Math.min(currmin*n,n)); max=Math.max(max,currmax); } return max; } }
Hi striver, first of all this is the best video that i have seen till now for this problem. Secondly, don't you think this is kadanes algorithm only. We did the same thing like adding all the elements till the end and when we got a negative element will turned that to 0. But this time we are doing from both the sides....
hey striver what about test case [-2 , 0 , -3] if we convert 0 to 1 and then compute prefix and suffix the answer comes out to be -2 but the actual answer is 0 how to go about that if anyone can explain
Do a try run, you will understand. The multiplication is done, and then the max is updated, and at the next step when you are at -3 the prefix is re-set to 1
I am just here to thank you for acknowledging that kadane's algorithm is not intuitive. I thought I was dumb for not being able to come up with kadane's intuition(while every other person I see is like - "oh yes kadane's algorithm, that’s so obvious").
Some comment i picked up from leetcode discussion to help out with intution : There are 2 possibilities - either the number of -ve numbers is even or odd. If they are even, then obviously we would want to include all of them(in fact the whole array(unless for zeros)) to maximise the product. This is because multiplying an even number of -ve numbers would make the result +ve. If they are odd, then we would want to exclude at most(to maximise the product) one -ve number from our product. So, now the question is, which -ve number to exclude? There are 2 possibilities - first -ve num or last -ve num. a. Note that, you cannot exclude a -ve number that is not the first or the last, because, if you do so, you will need to exclude all(because you are breaking the product at this point) other -ve nums following that -ve number and then that needn't result in the maximum product. b. Remember, that our goal is to leave out only 1 -ve number so that we can maximise our product. c. Note: We are leaving out one -ve number, so that we are able to make the number of -ve nums even. Having said all that, now the question is whether to exclude the first -ve num or the last -ve num in the array. We can only know the answer by trying both. d. By taking the product from the beginning of the array, you forcefully include the first -ve number and exclude the last -ve number e. vice-versa for taking the product from the end To further explain 2d,e, let me take an example: Assume the array has an odd number of -ve nums. The first -ve num is -2 and the last -ve num is -3. So the array is .....-2.......-3....... The maximum product can either be made of all numbers from the beginning of the array to the first non-zero number just before -3, or from the end of the array to the first non-zero number just after -2. This is why we are considering two possible products, one from the beginning and one from the end. But wait, you might be thinking, why we are still continuing to multiply even beyond -3(forward iteration) or beyond -2 (backward iteration). That's all actually waste, as the product is only going to increase in negativity beyond those points. The maximum is already updated, so this doesn't affect at all.
152. Maximum Product Subarray This solution will stuck in the last test case due to integer constraint. You should put a preventive condition that if the answer >= 10^9 then simply return 10^9. as it is the maximum possible ans
after this video i will try to unlearn almost formulas which can be changed by these type of solution with same or less tc and try to develop these intuition
Just a small change in the code for those who are wondering why 191th test case is not passing on leetcode, just change the data type of ans, pre and suff to double so as to prevent overflow in the intermediate steps. It has much bigger range than long and long long. Btw great explaination striver!!
Saved me hours of wondering. Thanks mate appreciate it
Thanks a lot bro. I was searching for this for hours until I saw your comment.
Bro is the saviour.
works but cheating lol
@@secondthread-uc9bd How's this cheating dude??
He is a real competitive programmer in all RUclipsrs who teaches DSA in India
guys who do cp have better problem solving skills, even doing dsa gives but cp just opens the brain to think in diff solutions
I had never seen this approach and the way you explain is like you own it.!!!
Superb work striver bro
;)
In leetcode take double for suffix,prefix and return value .so the last test case not gonna be int overflow
double maxPro = Integer.MIN_VALUE;
double pre = 1, suff = 1;
int len = nums.length;
for(int i=0; i
@@sumeetsinghaaryan why is it working for double but shows overflow error when using long?
@@shishirkarki9001 i also didnt get it ?
@@VISHALTHAKUR-gg3dg i came to know that double has larger range than long
thanks broooo
Completed this playlist also, MAN this is the best teacher of DSA. UNDERSTOOD!!!!!!!
You're God sent for us to learn in last moment ❤
I was literally searching for the intuitive approach and finally found it.. really appreciate it..
and a great explanation..
Arrays completed
Tomorrow I will revise full arrays before starting binary search
How
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.....
The way he did it in one go without taking separate arrays before and after 0 like I did.. hatsoff you are truly amazing!
bro no need any more examples you were the best in explaining this question with the most examples the cases...
Really understood the concept very well. Thank you for the video...
This approach is awesome! I've seen others teaching the same old Kadane approach, but this observation-based method is a real gem. Keep up the great work and keep sharing your insights!
The way he explained made me to think how to really approach a problem with logical thinking...Great Striver!!!
How can you help me please
Brilliant! this is actually much more intuitive as I was also thinking of applying prefix and suffix in it, just couldn't react to the final answer.
Thanks.
you are really the best teacher available on youtube
This will pass all testcases in leetcode
class Solution {
public:
int maxProduct(vector& nums) {
long long pre=1,suf=1;
long long maxi=INT_MIN;
for(int i=0;i
thanks bro
Best Solution , will never forget this solution .
bro, you are awesome, no one teaching the DSA like you teach us ..keep going, bro
Hey Striver can you add the famous Egg Dropping Problem in your DP series? It will be of great help to many students.
Had to give this a like, can't lie the best explanation for this problem.
I do not know who has observed the optimal approach but whoever the guy was, it was brilliant
Thanks for your explanation Striver
Understood it very well
And waiting for your Binary Search series...
i generally dont comment on videos , but yaar striver truly is a genius
Best explanations and best qualities. You are a striver indeed.
Was struggling to understand the explanation of this problem, but after tour video I am amazed how easy it is :D
Completed this playlist.... Gain confidence and knowledge.... Thank you Bhaiya ❤❤
Best explanation ever i have seen for this. Thank you bro 🙏
class Solution {
public:
int maxProduct(vector& nums) {
double prefix = 1, suffix = 1 , ans = INT_MIN;
int n = nums.size();
for(int i=0;i
The ans=max() part should come before we set the prefix and suffix as 1
Otherwise say in cases like [-ve ,0,-ve] the answer will be 1 instead of 0
Nice obs..
the solution was giving error for leetcode test case, so i put the finding max part before if condition , the solution got accepted
It should work if at the start you intitialize the max at min_int or min infinity in python. This way 0 will get picked. No need to change the max() part.
Another thing you can do is to store the maximum element of array in a maxele variable and return max(maxele,ans)
But the solution is giving runtime error on Leetcode
Java code for 191th test case:-
class Solution {
public int maxProduct(int[] nums) {
int n=nums.length;
if(n==0)return 0;
double ans= Integer.MIN_VALUE;
double pref=1, suf=1;
for(int i=0; i
I have watched the solution of neetcode and i must admit that you solution is very intuitive 😂
Happy to see your video. So many videos I watched for this question. Finally i can get the intutive for the question.
Hey Brother..At first thank you for your great work..Now I am learning Recursion from your recursion playlist..Love you from Bangladesh
Understood! Super awesome explanation as always, thank you very very very much for your effort!!
im so happy that i did this prblm both brute and optimal by myself....only difference in my code was i did traversal two times to calc prefix and suffix😅. BTW THANKS STRIVER YOU ARE GREAT🙇
The logical thinking It's very easy to understand.. with TC -> O(N) and SC -> O(1)
Agr apke jaise sir paid me bhi comtemt de toh public pakka legi 🫡🫡
You learn something new everyday ❤. This is the reason I love your videos. Got to learn something new.
I actually understand this and it makes so much sense. Thanks!
U jus explained the problem in a way it was made simple
Yes when I first saw the solution with kadanes it made me depressed fr, but this approach I will never forget
This solution works well except one edge case where we have a 0 in the array and even number of negative elements. In that case there is a possibility that 0 is our final answer if all other multiplications are negative. A simple tweak can help us solve this just maintain a zeroflag and before returning the answer just check if the answer is negative and the zeroFlag is set in that case we will simply return zero as our answer since we have a zero element in the array and the maximum subarray product excluding zero is negative.
But that's already covered.
Let's take an example as per your expl. :
-4 0 -5 , here 0 exists and even negative elements
In the first iteration pref=-4 suff = -5 , max=-5
second : pref=0 , suff=0 , max = 0
third : pref=-5 , suff=-4 , max=0
So we need not take any such flag or maybe you can specify any test case where your approach will work.!
UNDERSTOOD.............Thanks a ton............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
the best approach i have ever seen
if you're getting error due to testcases with starting or ending zeroes, then this solution should work:
#include
#include
using namespace std;
int subarrayWithMaxProduct(vector &arr){
int n=arr.size();
int pre=1, suff=1,maxprod=INT_MIN,prezero=0,suffzero=0;
for(int i=0;i
i have completed all the arrays but i am forgetting previous questions so give me advice so i can retain all the questions in my mind
Thanks for the great playlists for DSA
Thank You So Much for this wonderful video.......................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
One test case fails in leetcode using this solution. Below is the corrected code. Take prefix and suffix as double.
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE;;
double prefix = 1;
double suffix = 1;
for(int i=0; i
can please tell me the for taking it as double
awesome teaching and please teach every problem how to identify the pattern which algo we need to used.. and try to explain all the approaches. by the way your videos are great you will deserve 1m soon.
Nice Explanation and intuition for this problem.. Thanks a million Striver. ♥♥♥
Completed Arrays on 09/05/24 ..Superb Content and Explanation .....
Thanks for the great explanation, it feels like you are explaining me one to one the way you place your face on the screen!!
I think the super clean implementation was very nice.
u just fired it man.....what an awesome explanation....Thanks bro for the help.
I solved this problem using a extended version of kadane's algorithm:
class Solution {
public int maxProduct(int[] nums) {
int currmin=1,currmax=1,max=nums[0];
for(int n:nums)
{
int temp=currmax*n;
currmax=Math.max(currmax*n,Math.max(currmin*n,n));
currmin=Math.min(temp,Math.min(currmin*n,n));
max=Math.max(max,currmax);
}
return max;
}
}
double prefix = 1;
double suffix = 1;
pls consider this logic of double to prevent overflow of int data type in the test case of 190
This Guy is Next Level
After your hinting, I got the approach...but then I realized ,if we have 0s, then what to do
Hi striver, first of all this is the best video that i have seen till now for this problem. Secondly, don't you think this is kadanes algorithm only. We did the same thing like adding all the elements till the end and when we got a negative element will turned that to 0. But this time we are doing from both the sides....
class Solution {
public int maxProduct(int[] nums) {
int pre=1,suf=1,n=nums.length;
int ans=Integer.MIN_VALUE;
for(int i=0;i
will this interviewer ever be happy bro lol
Bhai mast video thi. Teeno algo's samajh mein aa gyin.
best explanation sir 😁😁
Thankyou Bro❤ I have Huge of respect and Thankfulness for you 🎉you are doing such a great thing ❤❤
Damn bro 🔥 i got it as asaf
amazing explanation just amaze with the approach
bro is this array playlist good?
@@PDSREACTION Not only array but all the playlists brothers without any doubt
superb and easy to understand explanation !
This approach is excellent.
Just another level 🔥
the optimal solution, too good and intuitive as you saidd!!!
Understood
Add checks at line 11 and 12, such that prefix and suffix product does not overflow integer limits.
if(prefix
Giving wrong answer at one test case😬
@@user-ym1nv1pw8i just assign double instead of int .
Test case is 3,0,-2,1 its giving wrong answer
finally array completed..thanks striver bhaiya
Nice solution
optimal approach is very intuitive .......but the one pass implementation is not......but u explained it very well
Understood striver much love to you
Leetcode overflow condition
public int maxProduct(int[] nums) {
double prefix = 1;
double suffix = 1;
int res = nums[0];
for(int i=0;i
explain why on changing long long to double giving the correct answer please explain anyone
hey striver what about test case [-2 , 0 , -3] if we convert 0 to 1 and then compute prefix and suffix the answer comes out to be -2 but the actual answer is 0 how to go about that
if anyone can explain
Do a try run, you will understand. The multiplication is done, and then the max is updated, and at the next step when you are at -3 the prefix is re-set to 1
@@takeUforward okay
It feels massively illegal to watch these videos for free
thank you so much!
Really needed this
mind blowing approach
really great explaination !!!
I am just here to thank you for acknowledging that kadane's algorithm is not intuitive. I thought I was dumb for not being able to come up with kadane's intuition(while every other person I see is like - "oh yes kadane's algorithm, that’s so obvious").
EXCELLENT
Array Ends.............
Huge respect brother♥
Some comment i picked up from leetcode discussion to help out with intution :
There are 2 possibilities - either the number of -ve numbers is even or odd.
If they are even, then obviously we would want to include all of them(in fact the whole array(unless for zeros)) to maximise the product. This is because multiplying an even number of -ve numbers would make the result +ve.
If they are odd, then we would want to exclude at most(to maximise the product) one -ve number from our product. So, now the question is, which -ve number to exclude? There are 2 possibilities - first -ve num or last -ve num.
a. Note that, you cannot exclude a -ve number that is not the first or the last, because, if you do so, you will need to exclude all(because you are breaking the product at this point) other -ve nums following that -ve number and then that needn't result in the maximum product.
b. Remember, that our goal is to leave out only 1 -ve number so that we can maximise our product.
c. Note: We are leaving out one -ve number, so that we are able to make the number of -ve nums even. Having said all that, now the question is whether to exclude the first -ve num or the last -ve num in the array. We can only know the answer by trying both.
d. By taking the product from the beginning of the array, you forcefully include the first -ve number and exclude the last -ve number
e. vice-versa for taking the product from the end
To further explain 2d,e, let me take an example:
Assume the array has an odd number of -ve nums. The first -ve num is -2 and the last -ve num is -3. So the array is .....-2.......-3.......
The maximum product can either be made of all numbers from the beginning of the array to the first non-zero number just before -3, or from the end of the array to the first non-zero number just after -2.
This is why we are considering two possible products, one from the beginning and one from the end.
But wait, you might be thinking, why we are still continuing to multiply even beyond -3(forward iteration) or beyond -2 (backward iteration). That's all actually waste, as the product is only going to increase in negativity beyond those points. The maximum is already updated, so this doesn't affect at all.
152. Maximum Product Subarray
This solution will stuck in the last test case due to integer constraint. You should put a preventive condition that if the answer >= 10^9 then simply return 10^9. as it is the maximum possible ans
NICE
I though this was about addition
My best DSA programming videos search ended here
I have solved this problem before, but still I would like to know your approach on this
the output of the array a[] = {-2,0,-1} is 0 . but as per above it returns 1
@takeUforward
can u explain it
Areh Dada ,,, watta approach
what about the case where zero will be the max product subarr
eg[-1,0,-2]
Great Approach!
Does Arrays ends here or I need to Binary Search Arrays as well to complete whole portion of Arrays?
Understood.
after this video i will try to unlearn almost formulas which can be changed by these type of solution with same or less tc
and try to develop these intuition
One solution for contiguous substring with starting and ending character is same