Free lesson · DSA Mastery - Interview Prep, End to End

Product of Array Except Self

Medium8 min readdsaarrays

Product of Array Except Self

This is one of the most asked array problems in interviews. The naive solution is straightforward; the optimal solution requires you to notice a clean observation about how prefixes and suffixes interact. And the follow-up - solving it with O(1) extra space (excluding the output) - pushes the elegance further.

The problem is essentially asking: at each position, compute the product of every element except the one at that position. The fascinating part is that you cannot use division (because of the zero-handling complication), which forces a more thoughtful approach.

The Problem

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.

Example 1:

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

Example 2:

Input:  nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: Any position with nums[i] != 0 has a product that includes 0,
             so answer[i] = 0. The position where nums[i] = 0 multiplies
             the other four values: (-1) * 1 * (-3) * 3 = 9.

Constraints:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix is guaranteed to fit in a 32-bit integer.

Follow-up: Can you solve the problem in O(1) extra space (the output array does not count as extra space)?

Approach

Why Not Use Division?

The simplest approach: compute the total product, then divide by nums[i] at each position. This breaks when any nums[i] is 0 (division by zero) or when handling sign carefully. The problem explicitly forbids division, but even without that rule, division creates correctness headaches with zeros.

Approach 1: Prefix and Suffix Arrays (O(n) time, O(n) space)

The key observation: answer[i] = (product of nums[0..i-1]) × (product of nums[i+1..n-1]).

So if we precompute:

• prefix[i] = product of nums[0..i-1] (everything to the left of i)
• suffix[i] = product of nums[i+1..n-1] (everything to the right of i)

Then answer[i] = prefix[i] × suffix[i].

Both prefix and suffix can be computed in O(n) by walking left-to-right and right-to-left respectively. This gives O(n) time and O(n) extra space.

Approach 2: O(1) Extra Space (excluding output)

The trick: compute the prefix products directly into the output array (left-to-right pass), then walk right-to-left maintaining a running suffix product as a single variable. At each position, multiply the prefix product (already in answer[i]) by the running suffix.

This gives O(1) extra space because the output array is not counted as extra by the problem statement, and we only use one running suffix variable.

graph TD
    A["Initialize answer array"] --> B["Pass 1: Left-to-right<br/>answer[i] = product of<br/>nums[0..i-1]"]
    B --> C["Pass 2: Right-to-left<br/>Track suffix product<br/>in a single variable"]
    C --> D["At each i, multiply<br/>answer[i] by suffix"]
    D --> E["Return answer"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the two-pass O of one space algorithm. The first pass fills the output array with prefix products: each position holds the product of all elements to its left. The second pass walks right-to-left, maintaining a single suffix-product variable, and multiplies each position by the current suffix product. After both passes, the output array holds the correct answer.

Code Implementation

public static int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    
    // Pass 1: prefix products
    // answer[i] will hold product of nums[0..i-1]
    answer[0] = 1;
    for (int i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }
    
    // Pass 2: multiply by suffix products
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= suffix;
        suffix *= nums[i];
    }
    
    return answer;
}

// Usage:
// productExceptSelf(new int[]{1, 2, 3, 4});       -> [24, 12, 8, 6]
// productExceptSelf(new int[]{-1, 1, 0, -3, 3});  -> [0, 0, 9, 0, 0]

This Java code implements the two-pass O of one space algorithm. The first loop fills answer with prefix products by walking left to right, starting with answer of zero equals one. The second loop walks right to left, maintaining a single suffix product variable, and multiplies each answer position by the current suffix before extending the suffix with the current element. The function returns the answer array.

The pivotal detail is the order of operations in the second pass: we multiply answer[i] by suffix before updating suffix with nums[i]. This is because the suffix product for position i should exclude nums[i] itself - suffix at that moment is the product of all elements to the right of i.

Walkthrough

Let us trace on [1, 2, 3, 4]. Expected output: [24, 12, 8, 6].

Pass 1: Prefix Products

Initial: answer = [_, _, _, _]

i=0: answer[0] = 1.                            answer = [1, _, _, _]
i=1: answer[1] = answer[0] * nums[0] = 1 * 1.  answer = [1, 1, _, _]
i=2: answer[2] = answer[1] * nums[1] = 1 * 2.  answer = [1, 1, 2, _]
i=3: answer[3] = answer[2] * nums[2] = 2 * 3.  answer = [1, 1, 2, 6]

At this point, answer[i] holds the product of everything to the left of position i. For position 3, that's 123 = 6.

Pass 2: Suffix Products

Initial: suffix = 1, answer = [1, 1, 2, 6]

i=3: answer[3] *= suffix.  answer[3] = 6 * 1 = 6.
     suffix *= nums[3] = 1 * 4 = 4.
     State: suffix = 4, answer = [1, 1, 2, 6]

i=2: answer[2] *= suffix.  answer[2] = 2 * 4 = 8.
     suffix *= nums[2] = 4 * 3 = 12.
     State: suffix = 12, answer = [1, 1, 8, 6]

i=1: answer[1] *= suffix.  answer[1] = 1 * 12 = 12.
     suffix *= nums[1] = 12 * 2 = 24.
     State: suffix = 24, answer = [1, 12, 8, 6]

i=0: answer[0] *= suffix.  answer[0] = 1 * 24 = 24.
     suffix *= nums[0] = 24 * 1 = 24. (irrelevant)
     State: answer = [24, 12, 8, 6]

Return [24, 12, 8, 6]. ✓

The mechanics: at each step, answer[i] already holds the prefix product, and suffix holds the suffix product. Multiplying them gives the final answer for position i.

Let us also trace [-1, 1, 0, -3, 3]. Expected: [0, 0, 9, 0, 0].

Pass 1: Prefix Products

answer = [1, _, _, _, _]
i=1: answer[1] = 1 * (-1) = -1.   answer = [1, -1, _, _, _]
i=2: answer[2] = -1 * 1 = -1.     answer = [1, -1, -1, _, _]
i=3: answer[3] = -1 * 0 = 0.      answer = [1, -1, -1, 0, _]
i=4: answer[4] = 0 * (-3) = 0.    answer = [1, -1, -1, 0, 0]

Pass 2: Suffix Products

Initial: suffix = 1, answer = [1, -1, -1, 0, 0]

i=4: answer[4] *= 1.   answer[4] = 0.
     suffix *= 3 = 3.

i=3: answer[3] *= 3.   answer[3] = 0 * 3 = 0.
     suffix *= -3 = -9.

i=2: answer[2] *= -9.  answer[2] = -1 * -9 = 9.
     suffix *= 0 = 0.

i=1: answer[1] *= 0.   answer[1] = -1 * 0 = 0.
     suffix *= 1 = 0.

i=0: answer[0] *= 0.   answer[0] = 1 * 0 = 0.

Return [0, 0, 9, 0, 0]. ✓

The zero at position 2 in the original array causes both the prefix and suffix to be zero for every other position. Position 2 itself is the product of everything else: (-1) * 1 * (-3) * 3 = 9. The algorithm gets this exactly right without any special-casing.

Complexity Analysis

Two passes through the array, each O(n). One auxiliary variable (suffix). The output array is not counted as extra space per the problem's definition.

Why Not O(n) Extra Space

If we counted the output array as space, the complexity would be O(n) - we are allocating an n-element array. But the problem explicitly says the output does not count. This is a common convention in problems where you must return an array.

If you genuinely need O(1) space including the output, you would have to modify the input array in place, which the problem does not require.

Why Two Passes Are Necessary

Each output position depends on values both to the left and to the right of it. A single pass can only see one direction at a time. The two-pass structure handles both directions: one pass for left-to-right (prefix), one pass for right-to-left (suffix).

There is no way to compute the answer in a single pass without precomputed information (like prefix arrays).

Variations & Follow-ups

What if you can use division?

If division is allowed and there are no zeros, the problem becomes trivial: total_product = product of all, then answer[i] = total_product / nums[i]. O(n) time, O(1) space.

With zeros, you have three cases:

• Zero zeros: standard division.
• Exactly one zero: answer[i] = 0 for i != zero_index, and answer[zero_index] = product of all non-zero elements.
• Two or more zeros: answer[i] = 0 for all i.

This works but is uglier than the prefix-suffix approach. The problem forbids it to force you to find the more elegant solution.

What if the input includes zeros (as in Example 2)?

The standard prefix-suffix algorithm handles zeros naturally. No special case needed. Trace Example 2 above to confirm.

Can you reduce to a single pass?

In principle, you would need to keep both prefix and suffix products as state. But to compute the suffix products from left to right, you would need to know the total product up front, which requires a pass. So no, two passes are inherent.

Why does the algorithm avoid integer overflow?

The problem guarantees that any prefix or suffix product fits in 32-bit. Since the final answer is just prefix × suffix, both factors fit in 32-bit, and the result fits per the problem's guarantee.

For unbounded inputs, you would need long arithmetic or BigInteger to avoid overflow. But the problem has bounded values (-30 to 30) and bounded length, so 32-bit is safe.

Interview-style framing

A clean answer in an interview:

1. State the brute force ("Multiply n-1 elements at each position: O(n²)").
2. Note the division approach ("With division, O(n) is easy - but the problem forbids it").
3. Identify the prefix-suffix structure ("answer[i] = prefix[i] × suffix[i]").
4. Code the two-array version for clarity.
5. Optimize to O(1) extra space by reusing the output array.

The interviewer is checking whether you can navigate the constraint (no division) and find the elegant alternative. The O(1)-space optimization is the follow-up that distinguishes a strong candidate from a great one.

The next topic is Next Permutation - another problem with a specific structural trick.

Back to DSA Mastery - Interview Prep, End to End