Product of Array Except Self

Approach Summary

Two passes: left pass builds prefix products, right pass multiplies suffix products into the result array.

Full Solution & Approach

The product of every element except self equals (product of everything to the left) times (product of everything to the right). The constraint says no division, so build those prefix and suffix products explicitly. In a first pass left to right, res[i] becomes the product of nums[0..i-1], computed by carrying a running prefix multiplier. In a second pass right to left, multiply each res[i] by the running suffix product of nums[i+1..n-1]. After both passes res[i] holds exactly the product of all elements except nums[i]. The trick is that both passes write into the same output array, so no extra arrays are needed. This is the canonical prefix/suffix pattern — the same skeleton (running left product, then the right product folded in) solves a whole family of array problems.

Two passes over n elements with constant work each — O(n) time. Only the output array plus two running variables, so O(1) extra space (the output array is excluded from the space count).

Solution Code

Solution

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [1] * n
    prefix = 1
    for i in range(n):
        res[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= suffix
        suffix *= nums[i]
    return res

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

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

vector<int> productExceptSelf(const vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, 1);
    int prefix = 1;
    for (int i = 0; i < n; i++) { res[i] = prefix; prefix *= nums[i]; }
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) { res[i] *= suffix; suffix *= nums[i]; }
    return res;
}

Edge Cases to Watch

A zero in the array — handled because we never divide
Multiple zeros — all products become 0 except the zeros' own entries
Two-element array — the left pass fills res[1], the right pass fills res[0]
Negative numbers — signs flow naturally through multiplication

How to Recognize This Pattern

No division allowed
Product of all except current

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)