238. Product of Array Except Self

The tell in this problem is the constraint: $O(n)$ time and no division. Division would make it trivial — total product divided by nums[i] — so banning it is what forces the prefix/suffix idea, and, as it turns out, what makes the answer survive zeros.

Question

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.

• Example1

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

• Example2

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

• Constraints
  • $2 <= nums.length <= 10^5$
  • $-30 <= nums[i] <= 30$
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
• Follow-up:
  • Can you solve the problem in $O(1)$ extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Algorithm

• Prefix Product with output array (space optimized)
  • TC: $O(n)$
  • SC: $O(1)$

Answer

/**
 * TC: O(n)
 * SC: O(1)
 */
public int[] productExceptSelf(int[] nums) {
    int len = nums.length;
    int[] result = new int[len];

    result[0] = 1;
    for (int i = 1; i < len; ++i) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    int suffix = 1;
    for (int i = len - 1; i >= 0; i--) {
        result[i] *= suffix;
        suffix *= nums[i];
    }

    return result;
}

Explain

Brute Force → Prefix Product

The most intuitive approach is to skip self and multiply the rest for each index.

// Brute Force: O(n²)
for (int i = 0; i < n; i++) {
    int product = 1;
    for (int j = 0; j < n; j++) {
        if (i == j) continue;  // skip self
        product *= nums[j];
    }
    result[i] = product;
}

This works but the inner loop runs n times for each of n elements → O(n²), which violates the O(n) requirement.

Why O(n²) → O(n)?

Looking at what the inner loop actually does:

result[i] = (product of everything left of i) × (product of everything right of i)

The inner loop computes both sides from scratch every time — that’s the waste.

The key insight: split the double loop into two single passes in opposite directions.

1st pass (→): pre-compute left products for every index
2nd pass (←): pre-compute right products and multiply on the fly

Each number is visited exactly once per pass → O(n).

Key Insight

The double loop computes left × right for each index from scratch every time.
Separating into two directional passes eliminates redundant computation → O(n²) → O(n).

Why the no-division rule is a gift

The tempting shortcut is to multiply the whole array once and divide nums[i] out. Beyond being banned, it breaks the moment the input holds a 0 — you’d divide by zero, and you’d need special cases for how many zeros there are. The prefix/suffix version never divides, so it handles zeros for free: run it on [-1,1,0,-3,3] and every slot except the zero’s own comes out 0, exactly as the two passes produce.

It also nails the follow-up. After the first pass, result already holds the left products; the second pass folds the right products in through a single suffix variable, so there’s no second array and the extra space is $O(1)$ (the output array doesn’t count).

References

• https://leetcode.com/problems/product-of-array-except-self/