Product of Array Except Self

medium array prefix product

Problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Inputnums = [2, 3, 4, 5]

Output[60, 40, 30, 24]

Position 0: 3·4·5 = 60. Position 3: 2·3·4 = 24.

nums (comma-separated)

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    pre = 1
    for i in range(n):
        out[i] = pre
        pre *= nums[i]
    suf = 1
    for i in range(n - 1, -1, -1):
        out[i] *= suf
        suf *= nums[i]
    return out

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

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

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> out(n, 1);
    int pre = 1;
    for (int i = 0; i < n; i++) { out[i] = pre; pre *= nums[i]; }
    int suf = 1;
    for (int i = n - 1; i >= 0; i--) { out[i] *= suf; suf *= nums[i]; }
    return out;
}

Explanation

For each spot we want the product of everything except the number there, and we are not allowed to use division. The idea is that this answer is simply (product of all numbers to the left) times (product of all numbers to the right).

We do it in two sweeps. In the first sweep (left to right) we set out[i] to pre, the running product of everything before i, then multiply pre by nums[i].

In the second sweep (right to left) we multiply out[i] by suf, the running product of everything after i, then update suf with nums[i]. After both sweeps, each out[i] holds left product times right product.

Example: nums = [2, 3, 4, 5]. After the left sweep out = [1, 2, 6, 24] (the prefix products). The right sweep then multiplies in the suffixes, giving [60, 40, 30, 24].

Because we reuse the output array for the prefix pass and only keep two running values, we need no division and barely any extra space.

Time: O(n) Space: O(1) beyond the output