Product of Array Except Self
mediumBlind 75NeetCode 150arraysprefix-sum
Problem
Given a list of integers, return a new list where each position holds the product of every other value in the original list. Solve it without using division.
Examples
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Each entry is the product of all other entries.
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Any entry sharing the list with a zero becomes zero, except the zero's own slot.
Constraints
- • 2 <= nums.length <= 10^5
- • The full product fits in a 32-bit integer
- • Division is not allowed
Hints(tap to reveal)
- 1. Each answer is prefix product times suffix product.
- 2. Two passes can build these without extra arrays.
Optimal approach(spoiler)
- Compute a running prefix product in a left-to-right pass, writing it into the output.
- Make a second right-to-left pass tracking a running suffix product.
- Multiply each output slot by the current suffix product.
- This avoids division and uses only the output array.
- O(n) time, O(1) extra space.
Ready to solve it?
Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.
Practice in the editor