Product of Array Except Self
Given an array nums of n integers where n > 1, return an array output such that each element at index i of output is equal to the product of all the numbers in the original array except nums[i].
Examples
nums = [1, 2, 3, 4] output: [24, 12, 8, 6] nums = [0, 0] output: [0, 0] nums = [4, 5, 1, 8, 2] output: [80, 64, 320, 40, 160] nums = [-2, 1, -3, 4, -1] output: [12, -24, 8, -6, 24]
Can you design an algorithm with a time complexity of O(n)?
Given an array nums of n integers where n > 1, the goal is to return an array output such that each element at index i of output is equal to the product of all the numbers in the original array except nums[i].
-
Initialization:
resultis initialized to store the final output, with all elements set to 1. We also initialize two variablesleftRunningProductandrightRunningProductto 1, which will be used to store the product of elements to the left and right of the current index, respectively. -
First Traversal (Left Product): We traverse the array from left to right. For each element at index
i, we setresult[i]to the current value ofleftRunningProduct. Then, we updateleftRunningProductby multiplying it withnums[i]. -
Second Traversal (Right Product): We traverse the array from right to left. For each element at index
i, we multiplyresult[i]by the current value ofrightRunningProduct. Then, we updaterightRunningProductby multiplying it withnums[i].
This approach ensures that result[i] contains the product of all elements except nums[i] after both traversals.
Example
Let's illustrate how the solution works:
Input array: nums = [4, 8, 2, 3] Initialization: result = [1, 1, 1, 1] leftRunningProduct = 1 rightRunningProduct = 1 First traversal (left product): result[0] = 1 leftRunningProduct = 1 * 4 = 4 result[1] = 1 * 4 = 4 leftRunningProduct = 4 * 8 = 32 result[2] = 1 * 32 = 32 leftRunningProduct = 32 * 2 = 64 result[3] = 1 * 64 = 64 leftRunningProduct = 64 * 3 = 192 After first traversal: result = [1, 4, 32, 64] Second traversal (right product): result[3] = 64 * 1 = 64 rightRunningProduct = 1 * 3 = 3 result[2] = 32 * 3 = 96 rightRunningProduct = 3 * 2 = 6 result[1] = 4 * 6 = 24 rightRunningProduct = 6 * 8 = 48 result[0] = 1 * 48 = 48 rightRunningProduct = 48 * 4 = 192 After second traversal: result = [48, 24, 96, 64] Final result = [48, 24, 96, 64]
Solution
def productExceptSelf(nums):
if len(nums) == 0:
return []
# Initialize the result array with ones
result = [1 for _ in nums]
# Compute the left product for each index
leftRunningProduct = 1
for i in range(len(nums)):
result[i] = leftRunningProduct
leftRunningProduct *= nums[i]
# Compute the right product for each index and update the result
rightRunningProduct = 1
for i in range(len(nums) - 1, -1, -1):
result[i] *= rightRunningProduct
rightRunningProduct *= nums[i]
return resultTime Complexity: The time complexity of this solution is O(n), where n is the number of elements in the input array nums. This is because we traverse the array three times (one pass to compute leftProduct, one pass to compute rightProduct, and one pass to compute the result).
Space Complexity The space complexity of this solution is O(n).
The result array, which is necessary to store the final output, requires O(n) space. The additional space used for the left and right running products is O(1) because they are single variables that do not scale with the input size.
Therefore, the total space complexity is O(n) due to the result array.
Check out our lesson on the two pass approach to learn more about it and its applications!
Watch an ex-Google software engineer answer the question "given an integer array, return an array response such that the i-th element of the output array is equal to the product of all the elements of the input array except for its i-th element."
If 0's aren't a concern, couldn't we just
if there's more than one zero, then we just return an array of 0s if there's one zero, then we just replace 0 with product and rest 0s.
what am i missing?