Product of Array Except Self
Given an array of integers, return an array of the same length where each element at index i is equal to the product of all numbers in the array except the one at index i.
Constraints:
- 1 <= nums.length <= 2 * 10^4
- -30 <= nums[i] <= 30
- 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 uses O(1) extra space (excluding output array).
Examples:
Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: For the input [1, 2, 3, 4], the output is [24, 12, 8, 6] because 24 = 2 * 3 * 4, 12 = 1 * 3 * 4, 8 = 1 * 2 * 4, and 6 = 1 * 2 * 3.
Solutions
Prefix and Postfix Product
The solution uses the concept of prefix and postfix products to calculate the product of all numbers except the one at each index. It first calculates the prefix product for each index and stores it in the answer array. Then, it calculates the postfix product for each index and multiplies it with the corresponding prefix product in the answer array.
def productExceptSelf(nums):
length = len(nums); answer = [1] * length; for i in range(1, length):
answer[i] = answer[i - 1] * nums[i - 1]; right = 1; for i in reversed(range(length)):
answer[i] *= right; right *= nums[i]; return answerFollow-up:
What if the input array contains zeros? How would you handle this case?
