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

[@GregHogg]

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

[@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

[@shreehari2589]

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

[@arsheyajain7055]

Literally the only video that helped!!! Thank you

[@GregHogg]

Glad to hear it 😎

[@helloworldcsofficial]

Good explanation. 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

[@kalan91]

@@kiattim2100I can’t see such rule, maybe they’ve updated the description. Now they encourage to find a solution with constant space. I did it this way and it passed.

[@ddogevandergraph1863]

Thank you, Greg!

[@amansingh-uu8uv]

here is my soulution which i think is much easy to understand and write from typing import List class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) ans_arr = [0] * n # Count zeros and calculate the product of non-zero elements zero_count = nums.count(0) if zero_count > 1: return ans_arr # More than one zero means all products are zero total_mult = 1 for num in nums: if num != 0: total_mult *= num # Fill the answer array based on the zero count for i in range(n): if zero_count == 0: ans_arr[i] = total_mult // nums[i] elif nums[i] == 0: ans_arr[i] = total_mult # Only the position with zero gets the product of non-zero elements return ans_arr

[@nishantmoolya]

I think only left prefix array and answer is enough rather and use a variable to store right sum and multiple It to prefix array

[@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!

[@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

[@stifferdoroskevich1809]

doesn't work when you have 0 in the array. The secont test case in leetcode fails

[@SpaceTalon]

Thanks!

[@GregHogg]

Very welcome :)

[@adityakhambeteIIT]

hey just want to say thanks

[@pemmasiva6296]

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

[@GregHogg]

You need to do both sides

[@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

[@tapoozz746]

damn, i literally was JUST about to ask this. youre awesome

[@rosseaton990]

@@tapoozz746 I'm trying to go about this the best way I can haha. Trying to get on Greg's level!

[@kalan91]

There’s much better and easier solution, that doesn’t use any extra space (other than result array). You have take into consideration a simple fact that each result element is simply a product of all of the elements DIVIDED by that element (for arrays without zeros). For array with zeros there are a few conditions like every number except that single 0 is going to be 0. They may be array with multiple zeros as well.

[@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.

[@jrob37]

amazing

[@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)

[@attenonmj3708]

How does a human being think of this...

[@GregHogg]

Lmao good question

[@Allyourneedsmet]

Especially knowing to use prefix and suffix numbers of 1

[@ledigdev]

bro what