🔁238. Product of Array Except Self
Medium | Grind 75 | July 25, 2022
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.
Constraints:
2 <= nums.length <= 105-30 <= nums[i] <= 30The product of any prefix or suffix of
numsis guaranteed to fit in a 32-bit integer.
Input: nums = [1,2,3,4]
Output: [24,12,8,6]SOLUTION:
The question asks you to find the product of every element except itself for all the elements. The main intuition behind this idea is that you need to somehow keep track of all the products that come before an element and all the products that come after the element.
Example 1:
In example 1, element 1 is 24 because 2x3x4 = 24. element 2 is 12 because 1x3x4 = 12 element 3 is 8 because 1x2x4 = 4 element 4 is 6 because 1x2x3 = 6
The way we will solve this problem is by having two lists that will store the products at each index. The first list will store products when we iterate from left to right (0 -> length of nums). the second list will store the products when we iterate from right to left (length of nums -> 0). This way we are aware of the products of all the elements before your target element and the product of all the elements after your target element. So, if we build the two lists for example 1, it would look the following.
Left (0 -> nums length) : [1,2,6,12] Right (nums length -> 0): [4,12,24,24]
Why do we need Left and Right? If you look at the two lists you will see that the values in the left list contain the products of all the elements until the particular index (value of particular index included). The values in the right list contain the products of all the elements until the particular index (value of particular index included). So let's look at Left.
LEFT: At index 0, we have 1. Given that there are no products before index 0, the product is the value itself. RIGHT: at index 0, from the right side we have 24.
LEFT: at index 1, we have 2 (2x1) RIGHT: at index 1, we have 24. (2x3x4)
It goes on like that until we reach the end of the list.
NOW, in order to calculate the product of all the elements excluding the target element, we just have to look at the element previous to the target elements index in our Left list and multiply that with the element next to the target elements index in our Right list.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
length = len(nums)-1
# left and right to store forward and backword product
right, left = [0]*(length+1), [0]*(length+1)
# 1. go from left to right and calculate the product, store in left
# 2. go from right to left and claculate the product, store in right
for i in range(len(nums)):
# look at the two ends of the value.
if i == 0:
# left -> right: doesn't have a previous.
# right -> left: doesn't have a next.
left[i] = nums[i]
right[length] = nums[length]
else:
# product of all elements until current element is curr element * the value at i-1 index of left list.
left[i] = nums[i]*left[i-1]
# product of all right most elements until current element is curr element * the value at length-i+1 index of right list.
right[length-i] = nums[length-i] * right[length-i+1]
result = [] # final result is an array of products.
for i in range(length+1):
if i == 0: # first element
result.append(right[1])
elif i == length: # last element
result.append(left[i-1])
else:
result.append(left[i-1]*right[i+1])
return result
Last updated