Product of Array Except Self

Build the output using prefix and suffix products in two passes without division

Complexity Analysis

Time Complexity O(n) Space Complexity O(1)

Time Complexity: O(n)

Breakdown

Pass 1 (prefix products): iterate indices 1 to n-1, one multiplication per index
Pass 2 (suffix products): iterate indices n-2 down to 0, two multiplications per index
Total operations: (n-1) + 2(n-1) = 3(n-1)
No nested loops, hash table lookups, or sorting

T(n) = (n-1) + 2(n-1) = 3n - 3 = O(n)

Mathematical Intuition

For each index i, the answer is product(nums[0..i-1]) × product(nums[i+1..n-1]). Computing each from scratch costs O(n) per index, totaling O(n²). The prefix/suffix decomposition precomputes running products so each element's answer is assembled in O(1) from previously computed partial products.

Key Insight

Prefix and suffix products are independent — the prefix at index i depends only on elements before i, and the suffix only on elements after i. This separability enables the two-pass linear solution.

Space Complexity: O(1)

Breakdown

Output array out: O(n) but excluded per problem definition
suffix: single scalar variable for running suffix product
Loop variable i: single integer
Input array is never modified

S(n) = O(1) — output array is not counted as extra space

Mathematical Intuition

A naive approach uses two separate O(n) arrays for prefix and suffix products. This optimization reuses the output array itself as the prefix array, then multiplies suffix products directly into it with only one extra variable. The output array serves dual purpose: storage for the answer and workspace for intermediate computation.

Key Insight

The output array is cleverly repurposed as scratch space: first it stores prefix products, then each entry is multiplied in-place by the running suffix. This eliminates the need for a separate suffix array.

Product of Array Except Self

Current Phase

Current Index (i)

Running Product

Output Value

Python Code

Time Complexity: O(n)

Space Complexity: O(1)