238. Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Reveal ↓
238. Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
#prefix
#left multiplication
p = 1
out = []
for i in range(len(nums)):
out.append(p)
p = p * nums[i]
#result of left multiplication [1,1,2,6]
#suffix - right multiplication from right side
p = 1
for i in range(len(nums) - 1, -1, -1):
out[i] = out[i] * p
p = p * nums[i]
# 1. i = 3, nums[3] = 4 ,out[3] = 6 * 1 = [1,1,2,6], p = 1 * 4(nums[3])
# 2. i = 2, nums[2] = 3, out[2] = 2 * 4 = [1,1,8,6], p = 4 * 3
# 3. i = 1, nums[1] = 2, out[1] = 1 * 12 = [1,12,8,6], p = 12 * 2
# 4. i = 0, nums[0] = 1, out[0] = 1 * 24 = [24, 12, 8, 6], p =24 * 1
return outarrayprefixsuffix