Product of Array Except Self - Leetcode 238 - Arrays & Strings (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@shreehari2589]

The way you explain stuff is awesome, keep up the good work and please also upload hard questions too

[@aimaalakhume]

Thanks, I love this solution! It was really easy to follow and I appreciate the concise code. I also never knew the zip() function existed

[@arsheyajain7055]

Literally the only video that helped!!! Thank you

[@GregHogg]

Glad to hear it 😎

[@adityakhambeteIIT]

hey just want to say thanks

[@jarodlatta6185]

I think you could get a constant time and space improvement by doing two passes through the array: first construct the product of all elements (unless they're 0), then iterate through again and divide the total by the current element. You do have go handle for 0s as a special case though, which might make it just as complex

[@kiattim2100]

You can't use division. That's the rule in leetcode 238

[@jarodlatta6185]

@@kiattim2100 ah okay, that makes sense

[@annas8308]

Hi Greg! What is the app you use to draw and teach us? I find it very easy to use and would like to take notes while viewing your videos.

[@GregHogg]

I use miro! It's really good for drawing:)

[@annas8308]

@@GregHogg Thank you, Greg!

[@SpaceTalon]

Thanks!

[@GregHogg]

Very welcome :)

[@jrob37]

amazing

[@rosseaton990]

This might seem trivial, but what does anyone suggest to do if you get stuck? I went ahead and just coded up the O(n^2) solution but for the life of me couldn't figure out the O(n) solution on my own. I also read up on prefix sum, as it was one of the topic tags on this question, but still couldn't think of the O(n) solution... Just trying to avoid going straight to the video solution when I get stuck

[@GregHogg]

I would incrementally get hints. So watch like the first few minutes of the video and if you get a lightbulb then turn it off and get coding

[@pemmasiva6296]

Small question
While filling the right array, why we are filling it from right to left?

[@GregHogg]

You need to do both sides

[@anirudd01]

there is a better and easy solution i think, we could just multiple all nums in the array , then keep dividing each of nums from the total product

[@sushantgarudkar108]

however the question states that you should not use division operation

[@phongnguyenhai3059]

what happen if 0 in array :D

[@arshiailaty]

Could you please let me know what you think of this solution? I should mention that there is a problem in the output when we have only one zero in numbers. The second if returns an array with all zeros.
import numpy
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
ans = []
ind = numpy.where(nums == 0)[0]
if len(ind) > 1:
return [0]*len(ind)
if len(ind) == 1:
i = ind[0]
res = numpy.prod(nums[:i]) * numpy.prod(nums[i+1:])
ans = [0]*len(nums)
ans[i] = res
return ans
product = numpy.prod(nums)
ans = [product // num for num in nums]
return ans

[@rishishah835]

What's the need to import numpy, the product function? Also, we're not allowed to use division, otherwise we could just iterate once -- get the total product, and then iterate through just dividing by each value in nums (unless 0)

[@Sanjay-bx6xb]

bro how do you come up with this logic

[@GregHogg]

Sometimes I might have figured it out, sometimes I might have just learned it elsewhere.

[@attenonmj3708]

How does a human being think of this...

[@GregHogg]

Lmao good question

[@Allyourneedsmet]

Especially knowing to use prefix and suffix numbers of 1