You are given a list of integers nums. Return a list answer of the same length, where
answer[i] is the product of every number in nums except nums[i].
Don't use division, and aim for O(n) time. (Dividing the total by nums[i] would fail anyway
when the list holds a zero.)
Example 1
- Input
- nums = [2, 3, 4, 5]
- Output
- [60, 40, 30, 24]
answer[1] is 2 × 4 × 5 = 40.Example 2
- Input
- nums = [3, 0, -2, 1]
- Output
- [0, -6, 0, 0]
answer[1] includes the zero.Constraints
numsholds 2 to 10⁵ numbers.- Every number is between −30 and 30.
- The product of any run of numbers in
numsfits in a 32-bit signed integer (−2³¹ to 2³¹ − 1).
Show the pattern
Prefix sums
Each answer is the product of everything to its left times everything to its right. Running products from each end, the multiplying cousin of prefix sums, give both in two passes.
See prefix sums in a visualiserShow the approach
Use two running products. On a left-to-right pass, set answer[i] to before, the product of
nums[0..i−1] (1 for the first position), then multiply before by nums[i]. On a right-to-left
pass, keep after, the product of the numbers to the right of i: multiply answer[i] by it,
then multiply after by nums[i].
Each position ends up with (product before it) × (product after it), which is everything except itself. There is no division, so zeros cause no trouble.
Time: O(n) · Space: O(1) besides the answer