Product Of Others
Problem
Given a list of integers, build a new list of the same length where each position holds the product of every other value in the input. The value at that position itself is left out of its own product. Solve it without using division, since a single zero in the input would make division impossible.
Examples
Input: nums = [2, 3, 4, 5]
Output: [60, 40, 30, 24]
Why: 3*4*5, 2*4*5, 2*3*5, 2*3*4Input: nums = [1, 0, 3]
Output: [0, 3, 0]
Why: only the slot facing the zero escapes itInput: nums = [0, 0, 7]
Output: [0, 0, 0]
Why: edge case, two zeros wipe out every positionHints
0 / 3
The answer at a position is really two independent pieces glued together: everything before it and everything after it.
Running products can be accumulated from the left and from the right, and each position needs one of each. Think about how to store both without two extra lists.
Sweep left to right writing the product of everything before each position into the output. Then sweep right to left carrying a running product of everything after, multiplying it into the value already sitting in each slot.
Solution
Every answer is the product of a prefix and a suffix, so two sweeps are enough. The first pass writes the running product of all earlier values into each slot, and the second pass multiplies in the running product of all later values while walking backwards. The output list doubles as the scratch space, so no extra structure is needed. Time is O(n) for the two passes, and space is O(1) beyond the returned list.
def products_excluding_self(nums):
n = len(nums)
out = [1] * n
prefix = 1 # product of everything to the left
for i in range(n):
out[i] = prefix
prefix *= nums[i]
suffix = 1 # product of everything to the right
for i in range(n - 1, -1, -1):
out[i] *= suffix
suffix *= nums[i]
return out
print(products_excluding_self([2, 3, 4, 5])) # -> [60, 40, 30, 24]
print(products_excluding_self([1, 0, 3])) # -> [0, 3, 0]
print(products_excluding_self([0, 0, 7])) # -> [0, 0, 0]Stuck on the idea rather than the code? Prefix Sums covers it.