Products of Array Except Self
Problem Statement
Given an integer array nums
, return an array output
where output[i]
is the product of all the elements of nums
except nums[i]
.
Each product is guaranteed to fit in a 32-bit integer.
Follow-up: Could you solve it in O(n)
time without using the division operation?
Example 1:
Input: nums = [1,2,4,6]
Output: [48,24,12,8]
Example 2:
Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]
Constraints:
2 <= nums.length <= 1000
-20 <= nums[i] <= 20
You should aim for a solution as good or better than O(n)
time and O(n)
space, where n
is the size of the input array.
Recommended Time and Space Complexity
You should aim for a solution as good or better than O(n)
time and O(n)
space, where n
is the size of the input array.
Hint 1
A brute-force solution would be to iterate through the array with index i
and compute the product of the array except for that index element. This would be an O(n^2)
solution. Can you think of a better way?
Hint 2
Is there a way to avoid the repeated work? Maybe we can store the results of the repeated work in an array.
Hint 3
We can use the prefix and suffix technique. First, we iterate from left to right and store the prefix products for each index in a prefix array, excluding the current index’s number. Then, we iterate from right to left and store the suffix products for each index in a suffix array, also excluding the current index’s number. Can you figure out the solution from here?
Hint 4
We can use the stored prefix and suffix products to compute the result array by iterating through the array and simply multiplying the prefix and suffix products at each index.
Solution
Brute Force
def product_except_self(nums: List[int]) -> List[int]: n = len(nums) res = [0] * n
for i in range(n): prod = 1 for j in range(n): if i == j: continue prod *= nums[j]
res[i] = prod return res
Time complexity: O(n^2)
Space complexity: O(1)