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].
Example:
Input:[1,2,3,4]Output:[24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.
Note: Please solve it without division and in O(n).
Source
def product_except_self(nums):
"""Using the following trick:
nums = [a, b, c, d, e ]
-----------------------------------------------
L = [1, a, ab, abc, abcd]
R = [bcde, cde, de, e, 1 ]
-----------------------------------------------
result = [bcde, acde, abde, abce, abcd]
Time Complexity: O(n)
Space Complexity: O(n)
"""
n = len(nums)
L, R, output = ([1]*n for _ in range(3))
# L[i] / R[i] = product of all the elements strictly to the left / right of i
for i in range(1, n):
L[i] = L[i-1]*nums[i-1]
R[n-1-i] = R[n-i]*nums[n-i]
for i in range(n):
output[i] = L[i]*R[i]
return output
nums = [1,2,3,4]
product_except_self(nums)
[24, 12, 8, 6]
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
def product_except_self(nums):
"""Solution with O(1) memory (2 passes)."""
n = len(nums)
output = [1]*n # output = L
R = 1 # we update R and build output along instead of using list
for i in range(1, n):
output[i] = output[i-1]*nums[i-1]
for i in range(n-1, -1, -1):
output[i] *= R
R *= nums[i]
return output
def product_except_self(nums):
"""Solution with O(1) memory (1 pass)."""
n = len(nums)
output = [1] * n
L = R = 1
for i in range(n):
output[i] *= L
output[~i] *= R # Reminder ~i = -1-i
L *= nums[i]
R *= nums[~i]
return output