# Python solution (Accepted), O(n) time, O(1) space

• ``````class Solution:
# @param {integer[]} nums
# @return {integer[]}
def productExceptSelf(self, nums):
p = 1
n = len(nums)
output = []
for i in range(0,n):
output.append(p)
p = p * nums[i]
p = 1
for i in range(n-1,-1,-1):
output[i] = output[i] * p
p = p * nums[i]
return output``````

• this is super brilliant.

• good solving. left to me, right to me .

• another approach if no overflow concerns.

``````def productExceptSelf(self, nums):
cntZero = nums.count(0)
if not cntZero:
prod = reduce(operator.mul,nums)
return [prod/x for x in nums]
res = [0]*len(nums)
if cntZero == 1:
res[nums.index(0)] = reduce(operator.mul,(x for x in nums if x))
return res
``````

• Sorry I am not very good with complexity. For your solution there are two for loop that loop through the len of nums. why is time complexity O(n) and not O(2n) ?

• @jienhua O(2n) is the same thing as O(n)

• @Aaron_Li thank you for the answer!

• It is brilliant, but seems not to be a right one.

• This post is deleted!

• This post is deleted!

• @qeatzy replace`reduce(operator.mul,(x for x in nums if x))` to `reduce(lambda x, y: x*y if y else x, nums)` can be much faster.

• @leefyi why?

• @hqpdash is this solution O(n) space instead of O(1) since we are using another output array to store numbers

• @hqpdash great!

• this is unbelievably brilliant! how did you come up with this amazing idea genius? I think it is not only a programming problem but even a math problem isn't it?

• This post is deleted!

• This post is deleted!

• @YaoshuaiZhang They are actually intelligence tests.

• In the case someone might be interested. This is the same approach but combining two pointers in one for loop.

``````class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""

if not nums: return False

arr = [1] * len(nums)
pi = pj = 1

for i in range(len(nums)):
j = -1-i

arr[i]*=pi; arr[j]*=pj
pi *= nums[i]; pj *= nums[j]

return arr

``````

• @qeatzy in interviews, this question tends to have an additional constraint that you can't use division in your solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.