LeetCode Product of Array Except Self: No Division

Intermediate 8 min read

What you'll learn

✓Why division is off-limits when zeros can appear
✓How prefix and suffix products combine to give the answer
✓How to use the output array as scratch space for O(1) extra memory
✓Common edge cases around zeros
✓How to defend the linear solution in an interview

Prerequisites

•Comfort with [arrays](/blog/arrays-introduction)
•Comfort with [Big-O notation](/blog/big-o-notation-explained)

Product of Array Except Self (LeetCode 238, Medium) is a perfect interview problem: 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]

Brute Force

For each index, multiply all other elements.

def product_brute(nums):
    n = len(nums)
    result = [1] * n
    for i in range(n):
        for j in range(n):
            if i != j:
                result[i] *= nums[j]
    return result

O(n^2). Works, but not the answer they want.

Optimal Solution

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, using the output array itself to avoid extra arrays.

def product_except_self(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

O(n) time, O(1) extra space (the output array does not count toward extra space).

Walk Through an 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].

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.

LeetCode 42 Trapping Rain Water (prefix/suffix max)
LeetCode 152 Maximum Product Subarray
LeetCode 560 Subarray Sum Equals K (prefix sums)
LeetCode 724 Find Pivot Index

Wrap up

Product of Array Except Self is the canonical prefix/suffix problem. 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.