Back to solutions

Product of Array Except Self

MediumArrays

For each index, output the product of all other elements, without using division.

Open problem
Constraints
  • 2 <= n <= 10^5
  • -30 <= nums[i] <= 30
  • The full answer fits in a 32-bit integer

Prefix and suffix products

Time O(n)Space O(1) extra (besides the output array)

The product of all elements except index i equals (product of everything to its left) times (product of everything to its right). Compute the left products in one forward pass, then multiply in the right products in one backward pass, reusing the output array so no extra space is needed.

Key terms
prefix product:
The running product of all elements before the current index.
suffix product:
The running product of all elements after the current index.
in-place accumulation:
Building the answer directly inside the output array instead of allocating separate left/right arrays.
vector<int> productExceptSelf(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;
}
Step by step
  1. Create res filled with 1s. Keep a variable prefix = 1.
  2. Forward pass: set res[i] = prefix (product of everything left of i), then multiply prefix by nums[i].
  3. Now res[i] holds only the left-side product for every i.
  4. Backward pass: keep suffix = 1; set res[i] *= suffix (folding in the right side), then multiply suffix by nums[i].
  5. After both passes res[i] = left product * right product = product of all except nums[i].
  6. No division is used and only the output array plus two scalars are needed.