Product of Array Except Self

MediumArray Prefix Sum

A pricing model multiplies a list of integer adjustment factors, nums. To see how much each factor matters, analysts want a leave-one-out report: for every position i, the product of all the factors except the one at i.

Return an array answer of the same length, where answer[i] is the product of every element of nums other than nums[i].

The algorithm must run in O(n) time and must not use division.
Factors can be negative or zero.
Every product of a prefix or a suffix of nums fits in a 32-bit signed integer, so every answer does too.

Example 1

Input: nums = [3,-2,5]
Output: [-10,15,-6]

Explanation: answer[0] = -2 · 5, answer[1] = 3 · 5 and answer[2] = 3 · (-2).

Example 2

Input: nums = [4,0,2,1]
Output: [0,8,0,0]

Explanation: Every other position multiplies by the zero. Leaving the zero itself out gives 4 · 2 · 1 = 8.

Example 3

Input: nums = [0,6,0]
Output: [0,0,0]

Explanation: With two zeros, every leave-one-out product still contains a zero.

Constraints

nums holds between 2 and 10^5 factors.
Each factor is an integer from -30 to 30.
Every prefix product and every suffix product of nums fits in a 32-bit signed integer.

Follow-up: The output array is unavoidable. On top of it, can you get by with only a constant number of extra variables?

💡 Hint 1

answer[i] is (product of everything to the left of i) × (product of everything to the right of i).

💡 Hint 2

Compute all the left products in one pass and all the right products in a second pass.

💡 Hint 3

To use O(1) extra space besides the output, store the left products in answer first, then sweep from the right with a single running product.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

The product of all elements except nums[i] equals the prefix product before i times the suffix product after i. First sweep left to right, writing into answer[i] the product of nums[0..i-1]. Then sweep right to left with a running suffix product: multiply answer[i] by suffix, then multiply suffix by nums[i]. Zeros need no special casing, and no division is used.

Time O(n)Space O(1) extra (the output array does not count)

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n);
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = prefix;
    prefix *= nums[i];
  }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }
  return answer;
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        int prefix = 1;
        for (int i = 0; i < n; i++) {
            answer[i] = prefix;
            prefix *= nums[i];
        }
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        return answer;
    }
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function productExceptSelf(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit