Product of Array Except Self — Prefix and Suffix, No Division

Product of Array Except Self (Medium) is a perfect interview question: trivial to brute force, sneaky to optimize, and the optimal trick generalizes everywhere. No division, O(n) time, O(1) extra space.

The Problem

Given an integer array nums, return an array answer such that answer[i] equals the product of all elements except nums[i]. You may not use division. Solve in O(n).

Example:

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

Intuition

The brute force is to multiply all other elements for each index. O(n^2). Fine for tiny inputs, dead on arrival otherwise.

The key idea: for each index i, the answer is prefix[i] * suffix[i] where prefix is the product of everything to the left and suffix is the product of everything to the right. Compute both in two passes. Better still, store the prefix products directly into the output array, then multiply each cell by a running suffix in a backward pass. That gives O(n) time and O(1) auxiliary space (the output array does not count toward extra space by the standard convention).

Division would be a one-pass trick: divide the total product by nums[i]. The catch is zeros. If any element is zero, division blows up. So the no-division rule forces the prefix/suffix approach.

Explanation with Example

nums = [1, 2, 3, 4].

• Forward pass: result = [1, 1, 2, 6] (each cell holds the product of everything to its left).
• Backward pass with suffix starting at 1:
  • i=3: result[3] = 6 * 1 = 6, suffix = 4.
  • i=2: result[2] = 2 * 4 = 8, suffix = 12.
  • i=1: result[1] = 1 * 12 = 12, suffix = 24.
  • i=0: result[0] = 1 * 24 = 24.
• Final: [24, 12, 8, 6].

index :     0     1     2     3
nums  : [   1     2     3     4 ]

prefix: [   1     1     2     6 ]   product of LEFT
suffix: [  24    12     4     1 ]   product of RIGHT

answer = prefix * suffix (element-wise)
    = [  24    12     8     6 ]

pass 1 (left -> right):    result holds prefix products
result = [ 1 , 1 , 2 , 6 ]
                            prefix var: 1 -> 1 -> 2 -> 6 -> 24

pass 2 (right -> left):    multiply by running suffix
suffix = 1
i=3: result[3] *= 1    -> 6
     suffix *= 4       -> 4
i=2: result[2] *= 4    -> 8
     suffix *= 3       -> 12
i=1: result[1] *= 12   -> 12
     suffix *= 2       -> 24
i=0: result[0] *= 24   -> 24

Code

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

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

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

Edge Cases

• One zero in the array: every index except the zero’s position gets 0; the zero’s index gets the product of the rest.
• Two or more zeros: every result is 0.
• Negative numbers: signs propagate naturally; no special handling needed.
• Length-2 input like [3, 5]: returns [5, 3].
• All ones: returns all ones.

Complexity Analysis

• Brute force: O(n^2) time, O(1) extra.
• Two-pass prefix/suffix: O(n) time, O(1) extra (excluding output).

The output array is not counted as auxiliary space per the standard convention; interviewers usually accept that explicitly.

How to Explain It in an Interview

State the constraint first: “no division, so I can’t compute the total product and divide out.” Then propose the prefix/suffix decomposition: answer[i] = (product of left) * (product of right). Show that you can store the left products in the output array in one pass, then multiply each cell by a running right-product in a second pass. The space optimization detail (reusing the output) is the senior-signal move; mention it explicitly.

Related Problems

• Trapping Rain Water (prefix/suffix max)
• Maximum Product Subarray
• Subarray Sum Equals K (prefix sums)
• Find Pivot Index

Wrap up

This is the canonical prefix/suffix question. Once you see the decomposition, dozens of array problems open up. Keep the two-pass with-reuse pattern in your back pocket; it shows up under many disguises.