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.

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.

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-1	$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
    }
}

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 would give an $O(n)$ single-pass solution, forbidden here because of how it handles zeros (and to force the prefix/suffix idea, which generalizes to many problems).

# 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([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)

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

Summary

Test cases

Related data structures

Related concepts

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