Skip to content
16-Week DSA Roadmap
LeetCode #238MediumProblem 6 of 8

Product of Array Except Self

For every position, multiply all the other numbers together, without using division.

  • Prefix and suffix products

Before this, know: Arrays and indexes, Loops that count down as well as up

The problem in plain English

You get an array of numbers nums. Build a new array answer of the same length where answer[i] is the product of every number in nums except nums[i]. (The product is what you get by multiplying numbers together.)

Example: nums = [1, 2, 3, 4].

nums
  1. 10
  2. 21
  3. 32
  4. 43
answer
  1. 240
  2. 121
  3. 82
  4. 63
answer[0] = 2 × 3 × 4 = 24, answer[1] = 1 × 3 × 4 = 12, answer[2] = 1 × 2 × 4 = 8, answer[3] = 1 × 2 × 3 = 6.

The rules that matter:

  • You may not use division. This is the whole challenge (more on why below).
  • It must run in O(n) time: a fixed number of passes over the array, no nested loops. (Big-O notation is a short way of saying how the work grows as the input grows; O(n) means “double the array, double the work”. See Big-O in 5 minutes.)
  • Numbers can be negative or zero. Every product fits in a normal 32-bit integer.
  • Follow-up: use only O(1) extra space (the answer array itself doesn’t count).

Before you code: think it through

Our problem is the same with multiplication instead of counting. For any index i, “everything except me” splits into two parts: everything to my left and everything to my right.

left of index 2
  1. 10
  2. 21
  3. 32
  4. 43
right of index 2
  1. 10
  2. 21
  3. 32
  4. 43
For index 2 (the 3): the left part is 1 × 2 = 2, the right part is 4. answer[2] = 2 × 4 = 8.

A running product from the left is called a prefix product (“prefix” means “the beginning part”); a running product from the right is a suffix product (“the end part”).

Pause and think

Why not multiply everything together once (1 × 2 × 3 × 4 = 24) and then divide by nums[i]? What happens with nums = [3, 0, 5]?

Approach 1: Brute force

For each index i, walk the whole array and multiply every number except nums[i].

Brute force: multiply everything else

nums = [1, 2, 3, 4]

nums
  1. 10
  2. 21
  3. 32
  4. 43
answer
  1. empty
variables
product
1
multiplications
0
  • Slot we're filling (i)
  • Multiplying in (j)
  • Skipped (j = i)
  • Just written

j = i = 0: skip ourselves.

Step 1 / 21

Which line is running?

function productExceptSelf(nums) {  const answer = [];  for (let i = 0; i < nums.length; i++) {    let product = 1;    for (let j = 0; j < nums.length; j++) {Running now:       if (j !== i) product *= nums[j]; // skip ourselves    }    answer.push(product);  }  return answer;}

Brute force

function productExceptSelf(nums) {  const answer = [];  for (let i = 0; i < nums.length; i++) {    let product = 1;    for (let j = 0; j < nums.length; j++) {      if (j !== i) product *= nums[j]; // skip ourselves    }    answer.push(product);  }  return answer;}
def product_except_self(nums):    answer = []    for i in range(len(nums)):        product = 1        for j in range(len(nums)):            if j != i:                product *= nums[j]  # skip ourselves        answer.append(product)    return answer

Why is it slow?

For each of the n slots we walk all n numbers: n × n steps. With 4 numbers that’s 16, fine. With 100,000 numbers (LeetCode’s limit) it’s 10,000,000,000 steps. That’s O(n²), and it breaks the O(n) rule.

The waste: answer[2] multiplies 1 × 2, and then answer[3] multiplies 1 × 2 again (then × 3). We keep redoing the same left-hand products.

Why division is banned, and what zeros do

The “obvious” shortcut is: total product ÷ nums[i]. Interviewers ban it because it hides the real skill (reusing partial products), and because of zeros:

  • One zero, like [-1, 1, 0, -3, 3]: every slot except the zero’s own slot gets 0 (they all include the zero). The zero’s slot gets the product of the others, 9. Division would need 0 ÷ 0 there.
  • Two or more zeros, like [0, 2, 0]: every slot includes at least one zero, so everything is 0.

Prefix and suffix products handle both cases with no special code. Play the zero examples in the visualizer below to see it.

The pattern: prefix and suffix products

Pattern

Prefix and suffix products (running totals)

Template

Use it when: each position needs a summary of everything before it, after it, or both.

Signal words

  • “except self”
  • “everything to the left”
  • “running total”
  • “prefix sum”
  • “range sum”
  • “without division”

Approach 2: Prefix pass, then suffix pass

  1. Fill answer with 1s. Set prefix = 1 (the product of nothing is 1, just as the sum of nothing is 0).
  2. Pass 1, left to right. For each i: write answer[i] = prefix (everything left of i), then update prefix *= nums[i] so it’s ready for i + 1.
  3. Set suffix = 1.
  4. Pass 2, right to left. For each i: multiply answer[i] *= suffix (everything right of i), then update suffix *= nums[i].
  5. Return answer.

Press Play. In pass 1 the shaded part of nums is what prefix has multiplied so far; in pass 2 it’s what suffix has multiplied. Watch each answer slot get its left half, then its right half. Then try the zero examples.

Prefix pass, then suffix pass

nums = [1, 2, 3, 4]

nums
  1. 10
  2. 21
  3. 32
  4. 43
answer
  1. 10
  2. 11
  3. 12
  4. 13
variables
pass
—
prefix
1product LEFT of i
suffix
—product RIGHT of i
  • Looking at now
  • Folded into prefix / suffix
  • Just written
  • Final value

Fill answer with 1s and set prefix = 1. prefix will always be the product of every number to the LEFT of i. Nothing is left of index 0, and multiplying by nothing gives 1.

Step 1 / 19

Which line is running?

function productExceptSelf(nums) {  const n = nums.length;Running now:   const answer = new Array(n).fill(1);  let prefix = 1; // product of everything LEFT of i  for (let i = 0; i < n; i++) {    answer[i] = prefix;    prefix *= nums[i];  }  let suffix = 1; // product of everything RIGHT of i  for (let i = n - 1; i >= 0; i--) {    answer[i] *= suffix;    suffix *= nums[i];  }  return answer;}

The order inside each loop matters: write first, then fold in nums[i]. That’s what keeps nums[i] out of its own answer.

The code, line by line

Prefix pass, then suffix pass

function productExceptSelf(nums) {  const n = nums.length;  const answer = new Array(n).fill(1);  let prefix = 1; // product of everything LEFT of i  for (let i = 0; i < n; i++) {    answer[i] = prefix;    prefix *= nums[i];  }  let suffix = 1; // product of everything RIGHT of i  for (let i = n - 1; i >= 0; i--) {    answer[i] *= suffix;    suffix *= nums[i];  }  return answer;}
def product_except_self(nums):    n = len(nums)    answer = [1] * n    prefix = 1  # product of everything LEFT of i    for i in range(n):        answer[i] = prefix        prefix *= nums[i]    suffix = 1  # product of everything RIGHT of i    for i in range(n - 1, -1, -1):        answer[i] *= suffix        suffix *= nums[i]    return answer

Lines 1–7 match in both languages. After that JavaScript has extra closing braces, so its line numbers run ahead.

  • Line 1: define the function. (LeetCode: var productExceptSelf = function(nums) in JS, def productExceptSelf(self, nums) in class Solution in Python.)
  • Line 3: an array of n ones. new Array(n).fill(1) / [1] * n. Starting at 1 matters: multiplying by 1 changes nothing.
  • Line 4: prefix starts at 1, because nothing is left of index 0.
  • Line 5: walk left to right.
  • Line 6: store “everything left of i” in the answer slot. nums[i] isn’t in prefix yet, which is exactly right.
  • Line 7: now include nums[i], ready for the next index.
  • Lines 9–10 (JS) / lines 8–9 (Python): suffix starts at 1 and we walk from the last index down to 0. In Python range(n - 1, -1, -1) means “start at n − 1, stop before −1, step −1”.
  • Line 11 (JS) / line 10 (Python): multiply in “everything right of i”. Now answer[i] is left × right, its final value.
  • Line 12 (JS) / line 11 (Python): include nums[i] in suffix for the next index to the left.
  • Last line: return the filled array.

Dry run

passiwrite into answer[i]then updateanswer afterwards
1 →0prefix = 1prefix = 1 × 1 = 1[1, 1, 1, 1]
1 →1prefix = 1prefix = 1 × 2 = 2[1, 1, 1, 1]
1 →2prefix = 2prefix = 2 × 3 = 6[1, 1, 2, 1]
1 →3prefix = 6prefix = 6 × 4 = 24[1, 1, 2, 6]
2 ←36 × suffix 1 = 6suffix = 1 × 4 = 4[1, 1, 2, 6]
2 ←22 × suffix 4 = 8suffix = 4 × 3 = 12[1, 1, 8, 6]
2 ←11 × suffix 12 = 12suffix = 12 × 2 = 24[1, 12, 8, 6]
2 ←01 × suffix 24 = 24suffix = 24 × 1 = 24[24, 12, 8, 6]
nums = [1, 2, 3, 4]

After pass 1 (its last row, i = 3) answer is [1, 1, 2, 6]: just the left halves. Pass 2 multiplies in the right halves from the end. The final products prefix = 24 and suffix = 24 are the total product, which we never use. That’s fine.

Complexity

Brute force

Time

O(n²)

For each of n slots we multiply up to n numbers.

Space

O(1)

Just a running product, apart from the answer array.

Prefix pass, then suffix pass

Time

O(n)

Two passes over the array, each doing one write and one multiply per index. 100,000 numbers ≈ 200,000 steps.

Space

O(1) extra

Only prefix and suffix. The answer array is the required output, so LeetCode doesn't count it.

A common middle version builds two separate arrays, left[i] and right[i], then multiplies them. That’s also O(n) time but uses O(n) extra space. Our version stores the left products directly in answer and keeps the right product in a single variable.

Common mistakes and edge cases

What to say out loud, in this order:

  1. “answer[i] is the product of everything to the left times everything to the right.”
  2. “Brute force recomputes these: O(n²). Running products reuse them.”
  3. “Two passes with one running variable each: O(n) time, O(1) extra space.”
  4. Explain why division fails with zeros, even if it weren’t banned.

Likely follow-up questions:

  • “Can you do it with O(1) extra space?” Yes, the solution above: the left products live in the output array.
  • “What about sums instead of products?” The same idea with prefix sums: total − nums[i] works for sums, since subtraction has no zero problem.
  • “Range queries: product or sum of nums[l..r]?” Precompute a prefix array once, then each query is one subtraction (sums) or careful division (products).

Related problems:

  • Two Sum and Contains Duplicate (this week): other “one pass, remember what you’ve passed” solutions.
  • Best Time to Buy and Sell Stock (week 2): carries a running minimum from the left, the same “summary of everything before me” idea as prefix.
  • Trapping Rain Water (not in this roadmap, but a classic): needs the tallest bar to the left and to the right of each position, a two-pass prefix/suffix problem just like this one.