For each index, return the product of all the other numbers. You cannot use division, and it must run in O of n.
DSA Animator › DSA Revision › Arrays › Product of Array Except Self
Remember: product except self equals left product times right product. Two passes, and the answer array doubles as storage. The video solves Product of Array Except Self (LeetCode 238, Medium) with the Prefix & Suffix pattern from the Arrays topic, and you can replay every step in the interactive Product of Array Except Self animation.
For each index, return the product of all the other numbers. You cannot use division, and it must run in O of n.
For 1, 2, 3, 4, the answer is 24, 12, 8, 6. For index 1, that is 1 times 3 times 4, which is 12.
Multiplying everything and dividing breaks on zeros, and division is not allowed anyway. Recomputing the product for every index is O of n squared.
Split it in two: the product of everything on the left, times the product of everything on the right. Build the left products in one pass, and multiply in the right products in a second pass.
Left pass: nothing is left of index 0, so it starts at 1. Then 1, then 1 times 2 is 2, then 2 times 3 is 6. The answer array now holds the left products: 1, 1, 2, 6. Right pass, from the end, with a running product called right, starting at 1. Index 3: 6 times 1 is 6, and right becomes 4. Index 2: 2 times 4 is 8, and right becomes 12. Index 1: 1 times 12 is 12, and right becomes 24. Index 0: 1 times 24 is 24. The answer is 24, 12, 8, 6.
In code, the first loop fills the answer with left products. The second loop goes backwards, multiplying in right, then updating right. That's O of n time, and O of 1 extra space besides the answer.
Remember: product except self equals left product times right product. Two passes, and the answer array doubles as storage.