mediumCodingEntryMidSenior
For every index, give me the product of all the other elements - and you cannot use division.
3 min readUpdated 2026-08-15
Answer
Short answer
Two passes over the array do it: a left-to-right pass writes the product of everything before each index into the output, then a right-to-left pass multiplies in a running product of everything after it.
Was this answer helpful?
Likely follow-ups
- If division were allowed, how would you handle exactly one zero, and then two zeros?
- This works for multiplication and addition. What property of the operation does the technique need?
- How would you serve thousands of range-product queries over a static array?
- Can you do the same thing in one pass if you are allowed to write into the output twice?
Related questions
- Rotate an array k positions to the right, in place.mediumAlso on arrays and in-place4 min
- Find the largest sum obtainable from a contiguous run of elements in an array.mediumAlso on arrays4 min
- Return every distinct triplet in the array that sums to zero.mediumAlso on arrays4 min
- Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.hardAlso on arrays5 min