LeetCode Day 15 - Product of Array Except Self

For every position of an array, compute the product of all other numbers. We can either use a known technique related to prefixes, or we can do some case analysis.

Subscribe for more educational videos on algorithms, coding interviews and competitive programming.

#Coding #Programming

[Errichto]

Regarding "what about O(1) space without division?" comments:
Leetcode editorial shows a solution that uses answer[n] as array to hold prefix products. That's stupid and obviously isn't O(N) space. If they wanted to require that, they should have said: try to use only one array of N integers, and I mentioned this in a video as an exercise (well, I just said that we can store prefix[n] and compute suffix products while going through the array). And yes, we can use the same array later to store the answer, but that's just very very bad programming practice.

[narayanbhat]

This video was much much better than past videos man, please provide in depth understanding for all the upcoming questions in the same way

[lovvyparhar]

Hey Errichto, can you please make a series on graph theory?

[prajwalparve]

Nice way to explain and really understand how programmers solve codes in contest.

[sizzle]

The way of thinking is so clear. It's valuable to understand what top programmers think at each step when they code.

[dcodernz]

You solved it better than the problem statement with prefix "product" (sum). Another great video. And you are right: The not using division statement is not very smart. It is the most efficient way you did it and the most understandable.

[jeetganatra]

Great how you as a great competitive programmer slows down and explains every bit of your thinking and approach
!! Also congratulations on the 100K !!

[kunalsahay]

this kind of explanation is what beginners crave for!
make videos like this from now on, without timer and thorough explanation.
Thanks

[kenteck]

It's good idea. You perform much clear without timer. Keep like that

[ztrixx]

Because of those last few seconds when you explained sufx and prefx..this video makes sense to me.. thank you!

[shubhankarsaha]

A much better leetcode 30 day challenge series video than the previous ones....

[bimalkumarsahoo]

most productive channel for me .. Thankyou for making me code everyday

[jimwoodward]

Great video -- really appreciate you explaining the prefix and suffix logic. Thank you!

[deepdhanuka]

Hey Errichto i think the better solution is to have just two integer variables i.e pref and suff and traverse the input array twice. In first traversal just pushback the prefix elements for the number and in second traversal traverse from nums.size()-1 to 0 multiplying all the suffixes correspondingly, in that way there is no division and it uses O(n) space

[linkus]

You can also notice, that there are at most around 30 elements > 1, so in the worst case, you will do O(N + 30*30) operations, if you recalculate the product without every integer > 1.

[JorgeIbanez]

Very good video Erichto! I was waiting for it cause here is almost 2:30 am jajaja

[adilammarbaig]

Keep it up Errichto, felt so much better today.
Request : could you consider making a conceptual series on a few commonly regarded difficult topics. Graph theory, DP, trees, etc.
Thank you.❤️

[happyhappyguy]

Errichto, I think for the follow up part, you need to do it with both constant memory and without division.

[jeff]

I love the video.It's more clear and suitable for beginners like me.Thank you

[multimoron]

You can do constant space without division using gcd storing only prefix and suffix products at i.