238. Product of Array Except Self (Medium)

Problem

Given an integer array nums, return an array answer such that answer[i] equals the product of all elements of nums except nums[i].

The algorithm must run in $O(n)$ time and must not use the division operation. Follow-up: can you solve in $O(1)$ extra space (the output array doesn’t count)?

Example

nums = [1, 2, 3, 4] → [24, 12, 8, 6]
nums = [-1, 1, 0, -3, 3] → [0, 0, 9, 0, 0]

LeetCode 238 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, nested product

For each i, multiply all other elements.

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)                              # L1: O(1)
    answer = [0] * n                           # L2: O(n)
    for i in range(n):                         # L3: outer loop, n iterations
        prod = 1                               # L4: O(1) reset
        for j in range(n):                     # L5: inner loop, n iterations
            if j != i:                         # L6: O(1) guard
                prod *= nums[j]                # L7: O(1) multiply
        answer[i] = prod                       # L8: O(1) assign
    return answer

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;                         // L1: O(1)
    const answer = new Array(n).fill(0);           // L2: O(n)
    for (let i = 0; i < n; i++) {                 // L3: outer loop, n iterations
        let prod = 1;                              // L4: O(1) reset
        for (let j = 0; j < n; j++) {             // L5: inner loop, n iterations
            if (j !== i) prod *= nums[j];          // L6-L7: O(1) guard + multiply
        }
        answer[i] = prod;                          // L8: O(1) assign
    }
    return answer;
}

func productExceptSelf(nums []int) []int {
  n := len(nums)                               // L1: O(1)
  answer := make([]int, n)                     // L2: O(n)
  for i := 0; i < n; i++ {                    // L3: outer loop, n iterations
    prod := 1                                // L4: O(1) reset
    for j := 0; j < n; j++ {               // L5: inner loop, n iterations
      if j != i { prod *= nums[j] }       // L6-L7: O(1) guard + multiply
    }
    answer[i] = prod                         // L8: O(1) assign
  }
  return answer
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (init output)	$O(n)$	1	$O(n)$
L3 (outer loop)	$O(1)$	n	$O(n)$
L5, L7 (inner loop + multiply)	$O(1)$	n² total	$O(n²)$ ← dominates
L8 (assign)	$O(1)$	n	$O(n)$

The nested multiply gives exactly n*(n-1) multiplications.

Complexity

Time: $O(n²)$ , driven by L5/L7 (nested loop multiplications).
Space: $O(1)$ excluding the output.

Too slow for the problem’s stated constraint but useful as a sanity check.

Swift

final class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        nums.indices.map { excluded in nums.indices.reduce(1) { product, index in index == excluded ? product : product * nums[index] } }
    }
}

Approach 2: Prefix and suffix products (two auxiliary arrays)

answer[i] = (product of everything left of i) × (product of everything right of i).

Compute both in $O(n)$ and combine.

Walkthrough: what each array entry means

The prefix and suffix products here are exclusive: they exclude the current element. An inclusive product would include it. Define what each slot contains before choosing indices:

prefix[k]: The product strictly to the left of nums[k].
suffix[k]: The product strictly to the right of nums[k].

These are sometimes called front and back. The names differ, but the meaning is the same. In Python slice notation, they summarize nums[:k] and nums[k + 1:]. Those slices describe the ranges, not extra lists the algorithm needs to create.

Use [2, 3, 4, 5] so accidentally skipping the first element changes the product:

index:       0     1     2     3
nums:       [2,    3,    4,    5]
prefix:     [1,    2,    6,   24]
suffix:     [60,  20,    5,    1]

At index 1, exclude 3. prefix[1] already contains 2, and suffix[1] already contains 4 * 5. Multiply those two entries at the same index:

Index `k`	Excluded value	`prefix[k]`: everything left	`suffix[k]`: everything right	`answer[k]`
0	`2`	`1` (nothing left)	`3 * 4 * 5 = 60`	`60`
1	`3`	`2`	`4 * 5 = 20`	`40`
2	`4`	`2 * 3 = 6`	`5`	`30`
3	`5`	`2 * 3 * 4 = 24`	`1` (nothing right)	`24`

index:       0     1     2     3
nums:       [2,    3,    4,    5]
prefix:     [1,    2,    6,   24]
             *     *     *     *
suffix:     [60,  20,    5,    1]
             =     =     =     =
answer:     [60,  40,   30,   24]

The product of an empty side is 1, the multiplicative identity: multiplying by it leaves the other side unchanged. That is why the combine step works at both ends without special cases.

Building an exclusive product: store, then update

A running accumulator makes the meaning explicit:

prefix = [1] * len(nums)
cur = 1
for i in range(len(nums)):
    prefix[i] = cur  # Everything before i, excluding nums[i].
    cur *= nums[i]  # Include nums[i] for the next iteration.

Before each iteration, cur is the product strictly to the left of i. Store it before multiplying in the current value. Starting this loop at 1 would skip nums[0] entirely: for this input, prefix[1] would incorrectly be 1 instead of 2.

The implementation below uses a different, equally valid construction: prefix[i - 1] * nums[i - 1]. It starts at 1 because prefix[0] is already initialized, and it explicitly incorporates nums[0] when computing prefix[1]. Loop bounds depend on how the stored product is built.

Common indexing and assignment mistakes

Mistake	Why it fails	Correct interpretation
`prefix[k - 1] * suffix[k + 1]`	At `k = 1`, this gives `1 * 5`, skipping both `2` and `4`.	Both arrays already exclude the current element. Use `prefix[k] * suffix[k]`.
`answer[0] = suffix[n - 1]`	The last suffix is the empty right side, so it is `1`.	Index `0` needs `suffix[0]`, which is `60` here.
`prefix[k] + suffix[k]`	Adding the two products does not multiply all remaining elements.	Combine the products with multiplication.
`answer = prefix[k] * suffix[k]` inside the loop	This replaces the entire list with a number.	Assign one slot: `answer[k] = prefix[k] * suffix[k]`.

The meaning of each entry determines the index. Moving to a neighboring slot is not needed just because the problem says to exclude the current element.

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)                              # L1: O(1)
    prefix = [1] * n                           # L2: O(n)
    suffix = [1] * n                           # L3: O(n)

    for i in range(1, n):                      # L4: forward pass, n-1 steps
        prefix[i] = prefix[i - 1] * nums[i - 1]  # L5: O(1)

    for i in range(n - 2, -1, -1):            # L6: backward pass, n-1 steps
        suffix[i] = suffix[i + 1] * nums[i + 1]  # L7: O(1)

    return [prefix[i] * suffix[i] for i in range(n)]  # L8: O(n)

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;                                  // L1: O(1)
    const prefix = new Array(n).fill(1);                    // L2: O(n)
    const suffix = new Array(n).fill(1);                    // L3: O(n)

    for (let i = 1; i < n; i++)                            // L4: forward pass, n-1 steps
        prefix[i] = prefix[i - 1] * nums[i - 1];          // L5: O(1)

    for (let i = n - 2; i >= 0; i--)                      // L6: backward pass, n-1 steps
        suffix[i] = suffix[i + 1] * nums[i + 1];          // L7: O(1)

    return prefix.map((p, i) => p * suffix[i]);            // L8: O(n)
}

func productExceptSelf(nums []int) []int {
  n := len(nums)                              // L1: O(1)
  prefix := make([]int, n)                    // L2: O(n)
  suffix := make([]int, n)                    // L3: O(n)
  prefix[0] = 1
  for i := 1; i < n; i++ {                   // L4: forward pass, n-1 steps
    prefix[i] = prefix[i-1] * nums[i-1]    // L5: O(1)
  }
  suffix[n-1] = 1
  for i := n - 2; i >= 0; i-- {             // L6: backward pass, n-1 steps
    suffix[i] = suffix[i+1] * nums[i+1]    // L7: O(1)
  }
  result := make([]int, n)
  for i := 0; i < n; i++ {
    result[i] = prefix[i] * suffix[i]      // L8: O(n)
  }
  return result
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2, L3 (init arrays)	$O(n)$	1 each	$O(n)$
L4, L5 (prefix pass)	$O(1)$	n-1	$O(n)$
L6, L7 (suffix pass)	$O(1)$	n-1	$O(n)$
L8 (combine)	$O(1)$ per element	n	$O(n)$

Three linear passes, each $O(n)$ . All three contribute equally; none dominates asymptotically.

Complexity

Time: $O(n)$ , driven by the three linear passes (L4/L5, L6/L7, L8).
Space: $O(n)$ for the two auxiliary arrays.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        let count = nums.count; var prefix = Array(repeating: 1, count: count), suffix = prefix
        for index in 1..<count { prefix[index] = prefix[index - 1] * nums[index - 1] }
        for index in stride(from: count - 2, through: 0, by: -1) { suffix[index] = suffix[index + 1] * nums[index + 1] }
        return zip(prefix, suffix).map(*)
    }
}

Approach 3: Space-optimized ( $O(1)$ extra space)

Reuse the output array for the prefix pass; track the suffix product as a single running scalar on a second pass.

Deriving the space optimization

The two-array approach keeps three arrays: prefixes, suffixes, and the answer. Remove storage in two steps:

Store the left products directly in answer. This array is required as the output, so a separate prefix array would duplicate those values.
Walk backward and generate each right product when it is needed. Once a suffix product has been used, the next iteration only needs that product multiplied by the current input value. A single variable can carry it.

After the forward pass, the output contains the old prefix array:

index:       0     1     2     3
nums:       [2,    3,    4,    5]
answer:     [1,    2,    6,   24]

Before each backward iteration, answer[i] still contains the product strictly to the left of i, and the scalar suffix contains the product strictly to its right. Multiply them, then include nums[i] in the scalar for the next iteration:

Index `i`	Left product in `answer[i]`	`suffix` before use	Updated `answer[i]`	`suffix` after including `nums[i]`
3	`24`	`1`	`24 * 1 = 24`	`5`
2	`6`	`5`	`6 * 5 = 30`	`20`
1	`2`	`20`	`2 * 20 = 40`	`60`
0	`1`	`60`	`1 * 60 = 60`	`120` (unused)

The final output is [60, 40, 30, 24]. Updating suffix before using it would include the very element we want to exclude. Overwriting answer[i] is safe: later iterations use their own untouched left products and the scalar, not the completed entries to their right.

This keeps only the state still needed. The output uses $O(n)$ storage, but the additional variables use $O(1)$ extra space. The algorithm does not need to modify nums.

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)                              # L1: O(1)
    answer = [1] * n                           # L2: O(n) output array

    # First pass: answer[i] = product of all elements left of i
    for i in range(1, n):                      # L3: n-1 steps
        answer[i] = answer[i - 1] * nums[i - 1]  # L4: O(1)

    # Second pass: multiply by product of all elements right of i
    suffix = 1                                 # L5: O(1) running scalar
    for i in range(n - 1, -1, -1):            # L6: n steps, right to left
        answer[i] *= suffix                    # L7: O(1) multiply-in-place
        suffix *= nums[i]                      # L8: O(1) extend suffix product

    return answer

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;                              // L1: O(1)
    const answer = new Array(n).fill(1);                // L2: O(n) output array

    // First pass: answer[i] = product of all elements left of i
    for (let i = 1; i < n; i++)                        // L3: n-1 steps
        answer[i] = answer[i - 1] * nums[i - 1];      // L4: O(1)

    // Second pass: multiply by product of all elements right of i
    let suffix = 1;                                     // L5: O(1) running scalar
    for (let i = n - 1; i >= 0; i--) {                // L6: n steps, right to left
        answer[i] *= suffix;                            // L7: O(1) multiply-in-place
        suffix *= nums[i];                              // L8: O(1) extend suffix product
    }

    return answer;
}

func productExceptSelf(nums []int) []int {
  n := len(nums)                           // L1: O(1)
  answer := make([]int, n)                 // L2: O(n) output array
  answer[0] = 1
  // First pass: answer[i] = product of all elements left of i
  for i := 1; i < n; i++ {               // L3: n-1 steps
    answer[i] = answer[i-1] * nums[i-1] // L4: O(1)
  }
  // Second pass: multiply by product of all elements right of i
  suffix := 1                              // L5: O(1) running scalar
  for i := n - 1; i >= 0; i-- {          // L6: n steps, right to left
    answer[i] *= suffix                  // L7: O(1) multiply-in-place
    suffix *= nums[i]                    // L8: O(1) extend suffix product
  }
  return answer
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (init output)	$O(n)$	1	$O(n)$
L3, L4 (prefix pass)	$O(1)$	n-1	$O(n)$
L5 (init suffix)	$O(1)$	1	$O(1)$
L6, L7, L8 (suffix pass)	$O(1)$	n	$O(n)$

Two linear passes, no auxiliary arrays. The suffix accumulator eliminates the need for a separate suffix[] array.

Complexity

Time: $O(n)$ , driven by L3/L4 and L6/L7/L8 (two linear passes).
Space: $O(1)$ extra (the output array is not counted per the problem).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        var result = Array(repeating: 1, count: nums.count), prefix = 1
        for index in nums.indices { result[index] = prefix; prefix *= nums[index] }
        var suffix = 1
        for index in nums.indices.reversed() { result[index] *= suffix; suffix *= nums[index] }
        return result
    }
}

How to recognize this pattern

The pattern is prefix/suffix accumulation. Here the summaries are exclusive products. The signal is an answer for every position that depends on everything except that position. Ask whether the remaining elements split into a left part and a right part whose summaries can be computed once and combined.

This avoids rebuilding almost the same product for every index. It also avoids needing an inverse operation to remove the current element from a total product. With zero in the input, naive total-product division cannot recover the answer at the zero’s position.

The same decomposition works with associative operations that have an identity, such as sum with 0 or product with 1. Preserve the original order when combining summaries. The operation and the information each answer needs determine whether the same space optimization is possible.

Connection	Shared reasoning	What differs
Array scans	Define what the running state means before the current element, then consume and update it in order.	This problem needs information from both directions.
Prefix sums	Reuse accumulated summaries instead of rescanning the input.	Range sums commonly subtract two checkpoints. Here we multiply disjoint left and right products.
42. Trapping Rain Water	Each position depends on summaries from both sides.	Left and right maxima determine the limiting water height, rather than products.

Why zeros and negative values need no special branches

The two sides contain every element except the excluded one, exactly once. Multiplication handles the values directly:

One zero: For [-1, 1, 0, -3, 3], only the position of the zero can have a nonzero answer. Its two sides multiply to 9. Every other position has that zero on one side.
Two zeros: For [2, 0, 4, 0], every position has at least one zero among the remaining elements, so all answers are zero.
Negative values: The signs follow ordinary multiplication. No separate sign logic is needed.
Two elements: For [2, 3], the left/right identities produce [3, 2] with the same loops.

Key takeaways

Define what a stored product includes before choosing indices. Exclusive left and right products combine at the same index.
Use a running product before including the current value when that value must be excluded.
Derive the follow-up by reusing the output for one side and generating the other side as needed.

Summary

Approach	Time	Space
Nested product	$O(n²)$	$O(1)$
Prefix + suffix arrays	$O(n)$	$O(n)$
Space-optimized	$O(n)$	$O(1)$ extra

Division is explicitly forbidden by the problem. Computing a total product and then dividing for each output would take separate passes and would need special handling for zeros. Prefix/suffix products satisfy the constraint directly.

# Quick smoke tests, paste into a REPL or save as test_product_except_self.py and run.
# Uses the canonical implementation (Approach 3: space-optimized).

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]
    return answer

def _run_tests():
    assert product_except_self([2, 3, 4, 5]) == [60, 40, 30, 24]
    assert product_except_self([2, 0, 4, 0]) == [0, 0, 0, 0]
    assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
    assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
    assert product_except_self([1, 1]) == [1, 1]
    assert product_except_self([2, 3]) == [3, 2]
    assert product_except_self([1, 0]) == [0, 1]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

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

console.assert(JSON.stringify(productExceptSelf([1, 2, 3, 4])) === JSON.stringify([24, 12, 8, 6]));
console.assert(JSON.stringify(productExceptSelf([-1, 1, 0, -3, 3])) === JSON.stringify([0, 0, 9, 0, 0]));
console.assert(JSON.stringify(productExceptSelf([1, 1])) === JSON.stringify([1, 1]));
console.assert(JSON.stringify(productExceptSelf([2, 3])) === JSON.stringify([3, 2]));
console.assert(JSON.stringify(productExceptSelf([1, 0])) === JSON.stringify([0, 1]));
console.log("all tests pass");

Arrays, input and output; classic prefix/suffix-product pattern

Array Scans, linear pass tactics for reading an array once, carrying just enough state, and avoiding nested loops.
Prefix Sums, accumulation tactics for answering range-sum and subarray-count questions from differences between checkpoints.

238. Product of Array Except Self (Medium)

Problem

Try it yourself

Approach 1: Brute force, nested product

Approach 2: Prefix and suffix products (two auxiliary arrays)

Walkthrough: what each array entry means

Building an exclusive product: store, then update

Common indexing and assignment mistakes

Approach 3: Space-optimized (O(1)O(1)O(1) extra space)

Deriving the space optimization

How to recognize this pattern

Why zeros and negative values need no special branches

Key takeaways

Summary

Test cases

Related data structures

Related concepts

Approach 3: Space-optimized ( $O(1)$ extra space)