Problem statement

Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i].

You must solve it without using division and in O(n) time.

Example 1

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

Example 2

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

Constraints

• 2 <= nums.length <= 10
• -4 <= nums[i] <= 4

Follow-up: can you do it in O(1) extra space (the output array does not count)?

Hints for Product of Array Except Self

1. Hint 1

   answer[i] equals (product of everything to the left of i) × (product of everything to the right).

2. Hint 2

   Two sweeps: one accumulating prefix products, one accumulating suffix products into the same output.

How to solve Product of Array Except Self

The product excluding index i is the product of everything to its left times everything to its right. Compute those two running products in two sweeps, and division is never needed — which matters because a single zero would make division impossible.

Approach

1. Sweep left to right, writing into answer[i] the product of all elements strictly before i.
2. Start that running product at 1, so the first entry is 1.
3. Sweep right to left with a second running product of everything strictly after i.
4. Multiply it into answer[i] as you go.
5. The output array itself carries the left products, so no third array is needed.

Why it works

Splitting at index i partitions the other elements into exactly two groups, so their products multiply to give the answer — no element is counted twice or missed. Doing it as prefix and suffix sweeps means each product is built incrementally rather than recomputed, giving linear time. It also handles zeros for free: a zero simply propagates into whichever side contains it, with no special-casing of one-zero or two-zero inputs.

Complexity

• Time — O(n)
• Space — O(1) extra, not counting the output

Pitfalls

• Division is forbidden, and would need awkward special cases for one zero and for two or more zeros.
• Both running products start at 1, the multiplicative identity.
• The products must exclude i itself — multiply before folding the current element into the running product.
• Reuse the output array for the left pass to keep the extra space constant.

Reference solution

Python

from typing import List

def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    out = [1] * n
    acc = 1
    for i in range(n):
        out[i] = acc
        acc *= nums[i]
    acc = 1
    for i in range(n - 1, -1, -1):
        out[i] *= acc
        acc *= nums[i]
    return out

Java

public static int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    int running = 1;
    for (int i = 0; i < n; i++) {
        answer[i] = running;
        running *= nums[i];
    }
    running = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= running;
        running *= nums[i];
    }
    return answer;
}

C++

vector<int> productExceptSelf(vector<int>& nums) {
    int n = (int) nums.size();
    vector<int> answer(n, 1);
    int running = 1;
    for (int i = 0; i < n; i++) {
        answer[i] = running;
        running *= nums[i];
    }
    running = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= running;
        running *= nums[i];
    }
    return answer;
}

JavaScript

var productExceptSelf = function(nums) {
    const n = nums.length;
    const out = new Array(n).fill(1);
    let acc = 1;
    for (let i = 0; i < n; i++) {
        out[i] = acc;
        acc *= nums[i];
    }
    acc = 1;
    for (let i = n - 1; i >= 0; i--) {
        out[i] *= acc;
        acc *= nums[i];
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium