Practice: Product Except Self
Left and right passes.
For each number in a list, find the product of all the other numbers. The catch is, you're not allowed to divide. Pause. How could you get everything to the left, and everything to the right?

- Product of all the others
- No division allowed
- Left and right?
Two sweeps
In the first sweep, going left to right, each position gets the product of everything before it. In the second sweep, going right to left, we multiply in the product of everything after it. Together, that's everything except the number itself. Run it. For one, two, three, four, the answers are twenty four, twelve, eight, and six.
def product_except_self(nums):
n = len(nums)
out = [1] * n
left = 1
for i in range(n):
out[i] = left
left *= nums[i]
right = 1
for i in range(n - 1, -1, -1):
out[i] *= right
right *= nums[i]
return out
print(product_except_self([1, 2, 3, 4]))[24, 12, 8, 6]
The prefix idea, again
This is the prefix sum idea, using products. The left sweep is a prefix product, and the right sweep is a suffix product. Many array problems become easy when you precompute what's to the left, and what's to the right, of every position.
| key | value |
|---|---|
| Left sweep | product before i |
| Right sweep | product after i |
| Combine | multiply them |
| Cost | O(n), no division |
Summary
A left sweep and a right sweep give the product of everything else, without division, in O of N. Next, trapping rain water.
Key takeaways- Prefix products
- Suffix products
- Multiply them