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

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

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

[shreehari]

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

[jarodlatta]

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

[annas]

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.

[RomanWaves]

damn i get this after breaking it down step by step. but i would never ever come about such an approach myself... i just started with DSA so maybe it just takes time... but its kinda weird. I consider myself fit at logic and maths, so the brute force way is pretty clear to me, but this effective way of algorithmic thinking just seems to be like a wall sometimes. do other guys here feel similiar ? is there a good approach to break though that barrier? or just coming back at it each day and keeping at it ? i mean i am not sure at which point i need to look up the solution. so when i really have no clue, then look it up ? sorry for the dumb question :D

[arsheyajain]

Literally the only video that helped!!! Thank you

[AsuAk]

Hi, loved the algo! Loved you more (best explanation, genius)!
Could we find the result of the multiplication (m) of all the elements first and just
output = [x for x in m//input[range(len(input))]] and do it? What can go wrong here?

[rosseaton]

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

[phanij]

class Solution:
def productExceptSelf(self, nums: list[int]) -> list[int]:
n = len(nums)
prefix = [1] * n # prefix product
suffix = [1] * n # suffix product

for i in range(1, n):
prefix[i] = prefix[i - 1] * nums[i - 1]

for i in reversed(range(n - 1)):
suffix[i] = suffix[i + 1] * nums[i + 1]

return [prefix[i] * suffix[i] for i in range(n)]

[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

[sookh.kitchen]

What is wrong with this solution?
Class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
i=0
product = []
while i<len(nums):
mult = prod(nums[:i]+nums[i+1:])
product.append(mult)
i+=1
return product

[pemmasiva]

Small question

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

[anirudd]

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

[amansingh-uuuv]

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

[Sanjay-bxxb]

bro how do you come up with this logic

[kalan]

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.

[attenonmj]

How does a human being think of this...