Product of Array Except Self

Given an integer array nums, build an array answer of the same length where answer[i] is the product of every element of nums except nums[i].

You may not use division, and your solution should run in O(n) time. Every product of a prefix or suffix of nums is guaranteed to fit in a 32-bit signed integer, so no overflow handling is needed.

As an extra challenge, try to use only O(1) extra space; the output array does not count towards that.

Example 1

Example 2

Example 3

Constraints

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums fits in a 32-bit signed integer.

Pattern Path · Math, Bits & Strings · problem 36 of 169

Start simple

For each index, multiply all the other elements with an inner loop: O(n²) time, O(1) extra space.

The key idea

For index i, the wanted product is (product of nums[0..i-1]) × (product of nums[i+1..n-1]). Both factors are prefix/suffix products, and those can be built incrementally: the left product for i + 1 is the left product for i times nums[i].

So walk left to right with a running value prefix (starting at 1), store it in answer[i], then multiply nums[i] into it. After this pass answer[i] holds everything to the left of i. Walk back right to left with a running suffix (starting at 1), multiply it into answer[i], then multiply nums[i] into suffix. Now each slot has both halves.

This avoids division entirely, which matters: dividing the total product by nums[i] breaks as soon as the array contains a zero. Zeros need no special case here, because each one simply lands in the left or right half of the other positions' products.

Complexity

• Time: O(n)
• Space: O(1) extra (the output array is not counted)

Python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        # Left pass: answer[i] = product of everything before i.
        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]

        # Right pass: multiply in the product of everything after i.
        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]

        return answer

JavaScript

var productExceptSelf = function(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);

  // Left pass: answer[i] = product of everything before i.
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = prefix;
    prefix *= nums[i];
  }

  // Right pass: multiply in the product of everything after i.
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }

  return answer;
};

What the interviewer is checking

The interviewer wants to see the prefix/suffix decomposition and whether you can squeeze it into the output array instead of allocating two helper arrays.

Mistakes to avoid

• Using total product divided by nums[i]: forbidden, and it fails on zeros.
• Off-by-one: answer[i] must exclude nums[i], so store the running product before multiplying the current element in.
• Allocating separate left and right arrays works but misses the O(1) extra-space goal.

Follow-ups to expect

• What if division were allowed? (Count zeros; handle 0, 1, 2+ zeros.)
• What if products could overflow? (Big integers or modular arithmetic.)
• How would you answer range products for many queries? (Prefix products or segment tree.)

In real software

The same left-pass/right-pass trick computes "everything except this one" aggregates, such as leave-one-out statistics in data analysis or gradients of a product in automatic differentiation.

Practice next