Product of Every Other Element

medium array prefix product

Problem

For each index i, return the product of every element in the array except nums[i]. Solve it without division by sweeping the prefix product left-to-right and the suffix product right-to-left, multiplying them in place.

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;
}

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