Given an integer array nums, return an array where each element at index i is the product of all elements in nums except nums[i]. You must solve it without using division and in O(n) time.
For example, given nums = [1, 2, 3, 4], the output is [24, 12, 8, 6] because: index 0 = 2*3*4 = 24, index 1 = 1*3*4 = 12, index 2 = 1*2*4 = 8, index 3 = 1*2*3 = 6.
Explain your approach without using division, walk through the algorithm, and analyze complexity.
How to approach it
- Hint 1
The product of all elements except self equals the product of everything to the left times the product of everything to the right.
- Hint 2
Build a prefix product array (left to right) and a suffix product array (right to left).
- Hint 3
You can optimize space by building the prefix products in the output array first, then multiplying by suffix products in a second pass.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.