[Leetcode]238. Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Note: Please solve it without division and in O(n).
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
Example:
Input: [1,2,3,4] Output: [24,12,8,6]

An O(n^2) approach is easy to come up with, however, an O(n) is also not difficult with a small trick. We can do it with two-pass. On the first scanning, we store the accumulative products into an array; on the second scanning in the reversed order, we find the accumulative products along the scanning.

class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
ret = [1] * len(nums)
for i in range(1,len(nums)):
ret[i] = ret[i-1]*nums[i-1]
right = 1
for i in range(len(nums)-1,-1,-1):
ret[i] *= right
right *= nums[i]
return ret

Subscribe
Notify of