Product of Array Except Self
Given an integer array, return an array where position i holds the product of all elements except nums[i]. Division is not allowed and the solution must run in linear time.
- 2 ≤ n ≤ 10^5
- -30 ≤ nums[i] ≤ 30
- The products fit in a 32-bit integer
- No division
- Each answer splits into "everything to the left × everything to the right"
- No division — so build prefix and suffix aggregates
- Linear time on an aggregation over ranges
If many queries ask for an aggregate over [l, r] and the aggregate has an inverse (sum, XOR, product without zeros), precompute P[i] = agg(a[0..i)) once so every query becomes P[r+1] - P[l]. Combined with a hash map of seen prefix values it counts subarrays with a given sum in one pass; the inverse trick (difference array) makes range updates O(1).
Fill the output with prefix products: out[i] = product of nums[0..i-1]. Then sweep from the right with a running suffix product, multiplying out[i] by the product of nums[i+1..]. The two sweeps give each position the product of everything except itself using only the output array as storage.
- With division you could compute the total product and divide, but zeros need special-casing. Two explicit prefix/suffix arrays are the same idea with O(n) extra space.