Product of Array Except Self
Problem
Return an array where each position holds the product of every other element in the input. You may not use division, and the solution should run in linear time.
Examples
Constraints
- • 2 <= nums.length <= 10^5
- • -30 <= nums[i] <= 30
- • Every prefix and suffix product fits in a 32-bit integer
Hints & approach
Hint 1
The answer at i is (product of everything left of i) times (product of everything right of i).
Hint 2
Both of those can be built with a running product in one direction.
Hint 3
Store the left products in the output array, then sweep right to left with a single variable.
Approachtry the hints first
Make a first pass left to right, writing into output[i] the product of all elements before i. Then make a second pass right to left, keeping a running product of elements after i and multiplying it into output[i]. Each output cell ends up as left product times right product. Apart from the output array, only one extra variable is used.
Time O(n) · Space O(1) extra (output excluded)