L3 · FAANGTwo pointers~12 min · 5 tests

Product of Array Except Self

Return the product of all other elements for each index without division, using prefix and suffix products in O(n) time and O(1) extra space.

The problem

Return a list where out[i] is the product of every element of nums except nums[i]. Do not use division, and aim for O(n).

Examples

Example 1

Input

product_except_self([1, 2, 3, 4])

Expected output

[24, 12, 8, 6]

Example 2

Input

product_except_self([-1, 1, 0, -3, 3])

Expected output

[0, 0, 9, 0, 0]

+ 3 hidden tests on Submit — two zeros.

Edge cases to ask about

Zeros
Two zeros
Negatives

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · product_except_self

def product_except_self(nums):
    """out[i] = product of all nums except nums[i], no division."""
    # Write your solution here
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

Measure it

Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Multiply everything else, per index	O(n²)	O(1)
Total product ÷ nums[i]	O(n)	O(1)	Banned — and it breaks on zeros.
bestPrefix × suffix products	O(n)	O(1) extra	The output array holds prefixes; a running suffix fills in the rest.

Walkthrough of the optimal approach (try it yourself first)

out[i] = product of the elements before i × product of the elements after i. The first pass writes the running prefix product into out; the second pass, right to left, multiplies in a running suffix product. No division, so zeros are handled naturally, and the only extra memory is two numbers.

Complexity: O(n) time, O(1) space. Two linear passes; apart from the output array only two running products are kept.

Reveal the reference solution

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

The brute force, for comparison

def product_except_self(nums):
    out = []
    for i in range(len(nums)):
        p = 1
        for j, x in enumerate(nums):
            if j != i:
                p *= x
        out.append(p)
    return out

Follow-ups interviewers ask

Why does the division approach fail with zeros?

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Product of Array Except Self in Python?

The optimal solution runs in O(n) time and O(1) auxiliary space. Two linear passes; apart from the output array only two running products are kept.

What is the brute-force approach, and how do you optimise it?

Multiply everything else, per index: O(n²) time, O(1) space. Total product ÷ nums[i]: O(n) time, O(1) space. Banned — and it breaks on zeros. Prefix × suffix products: O(n) time, O(1) extra space. The output array holds prefixes; a running suffix fills in the rest.

What follow-up questions do interviewers ask about Product of Array Except Self?

Why does the division approach fail with zeros?