Algorithm

Product of Array Except Self

Arrays & Strings Pattern

Product of Array Except Self

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. You must write an algorithm that runs in O(N) time and without using the division operation.

CONSTRAINTS
  • 2 <= nums.length <= 10⁵
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix fits in a 32-bit integer
EXAMPLE 1
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
For index 2 (value 3): left piece is 1 × 2 = 2, right piece is 4. Answer there: 2 × 4 = 8.
EXAMPLE 2
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
One zero: every index except the zero's own has 0 in its product. At the zero's index, the product of the others is (-1) × 1 × (-3) × 3 = 9.
EXAMPLE 3
Input: nums = [0,4,0]
Output: [0,0,0]
Two zeros: every index — even the zeros themselves — has at least one zero on some side, so everything is 0.
Why exactly is division not allowed?
Partly to force the intended technique, but the restriction is also principled: with a zero in the array the division approach computes 0 ÷ 0 at the zero's index, so it is genuinely broken, not merely forbidden.
Does the output array count towards the space limit?
By convention, no — the answer has to exist somewhere. 'O(1) extra space' means beyond the output. Worth stating this assumption to the interviewer explicitly.
Can the numbers be negative?
Yes. Signs simply multiply through the prefix and suffix products — no special handling is needed.

Calculating the product of all elements except the current one is like making a "sandwich" for every index. Each result is the product of everything to the left of the index multiplied by everything to its right. The challenge is to do this in linear time without using division.

Quadratic Multiplications (O(N²))

The most direct way is to iterate through every index and, for each one, loop through the entire array again to multiply all other elements.

python
res = [1] * n
for i in range(n):
    for j in range(n):
        if i != j:
            res[i] *= nums[j]
return res
The Sandwich Logic

If division were allowed, we could find the total product and divide by each number. However, this is forbidden and becomes impossible if the array contains a zero. This forces us to find the "left-side product" and "right-side product" independently for every number.

Prefix & Suffix Arrays (O(N) space)

We can use two extra arrays to pre-calculate the "sandwich" parts for every index.

python
L, R = [1] * n, [1] * n
for i in range(1, n):
    L[i] = nums[i-1] * L[i-1]
for i in range(n-2, -1, -1):
    R[i] = nums[i+1] * R[i+1]

res = [L[i] * R[i] for i in range(n)]
return res
Two-Pass Space Optimization (O(1) space)

We can achieve the same result using only the output array as workspace.
1. Pass 1 (Forward): Fill the output array with the left-side (Prefix) products.
2. Pass 2 (Backward): Walk backwards and multiply those prefix products by a running right-side (Suffix) total.

python
res = [1] * n
# Pass 1: Left products
left = 1
for i in range(n):
    res[i] = left
    left *= nums[i]

# Pass 2: Right products
right = 1
for i in range(n-1, -1, -1):
    res[i] *= right
    right *= nums[i]
Worked Example:[1, 2, 3, 4]
- Pass 1 (Left Products): We walk forward and populate res with the product of all elements to the left.
0
1
1
1
2
2
3
6
We complete the forward pass, storing the product of all elements to the left of each index. The array now holds the prefix products.
- Pass 2 (Right Products): We walk backward, multiplying each spot by a running right suffix product.
0
1
1
1
2
2
3
6
i
At index 3, we multiply our prefix product of 6 by our running right product of 1, keeping the result 6. We then update our running right product to 4 (1 times 4).
0
1
1
1
2
8
i
3
6
At index 2, we multiply our prefix product of 2 by our running right product of 4, updating this index to 8. We then update our running right product to 12 (4 times 3).
0
1
1
12
i
2
8
3
6
At index 1, we multiply our prefix product of 1 by our running right product of 12, updating this index to 12. We then update our running right product to 24 (12 times 2).
0
24
i
1
12
2
8
3
6
At index 0, we multiply our prefix product of 1 by our running right product of 24, updating this index to 24. We have now finished our backward pass, yielding the final result.
Interactive Strategy Visualization

Product Pre-Computation

Strategy: Dual Pass Accumulation
Input
1
2
3
4
5
Result
1
1
1
1
1
Starting Left Pass. Index 0: Nothing to the left, so store 1.
DIVISION-FREE

By calculating Left and Right products separately, we avoid dividing by zero—a common pitfall in this problem.

SPACE-SAVER

We reuse the output array for our prefix pass and update it on the suffix pass, achieving O(1) extra space.

O(N²) Brute Force
→
O(N)/O(N) Prefix+Suffix Arrays
→
O(N)/O(1) Two-Pass Fold