DSAMotivator

Product of Array Except Self

Medium·🗂️ Arrays & Hashing·Open on LeetCode ↗

Return an array where each position holds the product of every other entry, without using division.

nums = [3, 2, 5, 4]step 1/10
3
2
5
4
0
1
2
3

Each answer is everything to the left, times everything to the right.

1def product_except_self(nums):
2    n = len(nums)
3    out = [1] * n
4    prefix = 1
5    for i in range(n):
6        out[i] = prefix
7        prefix *= nums[i]
8    suffix = 1
9    for i in range(n - 1, -1, -1):
10        out[i] *= suffix
11        suffix *= nums[i]
12    return out
Read the 10 steps as text
  1. 1Each answer is everything to the left, times everything to the right.
  2. 2Everything before index 0 multiplies to 1. Store it.
  3. 3Everything before index 1 multiplies to 3. Store it.
  4. 4Everything before index 2 multiplies to 6. Store it.
  5. 5Everything before index 3 multiplies to 30. Store it.
  6. 6Everything after index 3 multiplies to 1. Combine: index 3 is 30.
  7. 7Everything after index 2 multiplies to 4. Combine: index 2 is 24.
  8. 8Everything after index 1 multiplies to 20. Combine: index 1 is 60.
  9. 9Everything after index 0 multiplies to 40. Combine: index 0 is 40.
  10. 10Two sweeps, no division: [40, 60, 24, 30].

The idea

The obvious shortcut is to multiply everything and divide by each element. The problem bans division, and for a good reason — a single zero makes it collapse, and two zeros make it meaningless.

Without division, look at what each answer actually is: everything to the left of the position, times everything to the right. Two independent quantities.

Each of those is a running product, and a running product is free if you sweep in the right direction. Go left to right accumulating what came before; go right to left accumulating what came after. Multiply the two sweeps together and every position has its answer.

The neat part is that the output array itself can hold the first sweep, so the second sweep just multiplies into it. That's how this hits O(1) extra space — the answer array doesn't count.

The approach

  1. 1Sweep left to right, writing into each position the product of everything before it. The first position gets 1, because nothing precedes it.
  2. 2Sweep right to left carrying a running product of everything after the current position.
  3. 3Multiply that suffix into each position as you pass it.
  4. 4The output now holds left × right at every index.

Complexity

Time
O(n)
Space
O(1)

Two passes. The output array is excluded from the space count by convention, and the sweeps need only one extra variable each.

Code

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    prefix = 1
    for i in range(n):
        out[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        out[i] *= suffix
        suffix *= nums[i]
    return out

What goes wrong

  • •Writing the prefix into position i *after* multiplying it by nums[i], which includes the element in its own product. Write first, then accumulate — the order is the whole trick.
  • •Using division anyway. Beyond being disallowed, a single zero forces a special case and two zeros break it entirely.
  • •Allocating separate prefix and suffix arrays. It works and it's easier to read, but it gives up the O(1) space that this problem is really testing.