Given an array
numsof n integers where n > 1, return an array
output[i]is equal to the product of all the elements of
nums[i]. Note: Please solve it without division and in O(n). Follow up: 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:
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 =  * 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