def productExceptSelf(self, nums):
n = len(nums)
output = nums[:]
record = 1
for i in range(0, n): #nums[i] saves the product of original nums[0]*nums[1]*...*nums[i1]
if i > 0:
record, nums[i] = nums[i], record * nums[i1]
else:
record, nums[0] = nums[0], record
record = 1
for i in range(n1, 1, 1): #output[i] saves the product of original nums[n1]*nums[n2]*...*nums[i+1]
if i < n1:
record, output[i] = output[i], record * output[i+1]
else:
record, output[i] = output[i], record
for i in range(0, n):
output[i] = nums[i] * output[i]
return output
Python O(n), no extra space solution


@arun42 Hi, here is a line in the question description:
"Note: The output array does not count as extra space for the purpose of space complexity analysis"