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).
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.)
The description was taken from https://leetcode.com/problems/product-of-array-except-self/.
#O(N) Time, O(1) Spaceclass Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: length = len(nums) answer = [0]*length answer[0] = 1 for i in range(1, length): answer[i] = nums[i - 1] * answer[i - 1] right = 1 for i in range((length) -1, -1, -1): answer[i] = answer[i] * right right *= nums[i] return answerThe brute force approach would be to traverse through the input array. Within each iteration, we would have two nested loops. We would have one inner loop that would traverse from the current index to the beginning of the array, excluding the current index while multiplying that range, and another inner loop that would traverse from the current index to the end of the array, excluding the current index while multiplying that range then we would add those values together to update the output array with.
The problem with that is we would be recalculating the same ranges multiple times which would lead to quadratic time complexity. For example, by the time we got to the fourth index, we would be recalculating the product of the first, second, and third indices when we already calculated the product of the first and second indices within the previous iteration.
One better approach could be to create three arrays.
We could have an answer array, a left array, and a right array. We would traverse the values of the input array left to right. During each iteration, we would be setting our current element in the left array as the product of the previous element and the element in the corresponding index of the input array. We would do the same thing for the right array, but instead stepping right to left over the input array and taking the right-side products. We would finally traverse the answer array and set each element as the product of the two elements of the same index in right and left.
This would allow us to not recalculate the same product ranges for repeated work, but now we could throw the previous number product onto a snowball product from the previous iteration's product range calculation.
However, that would require linear time and space so it still isn't the optimal solution, but it's close.
What we could do instead is utilize the array we are returning to store the left product in place, then create a right integer that we would use to increment the current value by the product of everything to the right.
Let's start by saving the length of the array so that we don’t have to keep calculating this value.
length = len(nums)
Then, we’ll initialize an output array equal to the length of the input.
answer = [0]*length
We’ll set the first element in the output array equal to one since there is nothing is to the left of the first element within the input array and multiplying a number by one will equal itself.
answer[0] = 1
We’ll then use a loop to traverse the answer array left to right and multiply the previous element with the corresponding element of the input array.
Next, we will traverse the array from left to right, gathering the left product for each element.
for i in range(1, length): answer[i] = nums[i - 1] * answer[i - 1]
After, we’ll set our running right product value to one, for the same reason as setting the first element of the answer array to one mentioned previously.
right = 1
Now, we will traverse the array from right to left, gathering the right product for each element.
for i in range((length) -1, -1, -1): answer[i] = answer[i] * right
Afterward, we'll increment the running right value by the product of itself and the current index’s element. By doing this, when we access right in the next iteration, it will have essentially been multiplied by the right-side element in the answer array.
right *= nums[i]
We’ll return the answer array once our second traversal is done.
return answer
This solution may seem random, but it follows a similar idea as the popular Prefix Sum array which is very useful for avoiding the recalculation of the same ranges.
We are only making a couple of tweaks here. The first is that indices within prefix sum arrays signify the range sum between the beginning of the array up to the current index from the given input, and here we are excluding the current index from that range sum. The second is we aren't calculating range sums, but range products.