# Product of Array Except Self

[link](https://leetcode.com/problems/product-of-array-except-self/) · Medium · `array`, `prefix sum`, `prefix product`

> "combine everything except index i" (or "everything left of i" / "everything right of i") → prefix × suffix: one pass left-to-right, one pass right-to-left. Store one direction in the output and keep the other as a running variable for O(1) extra space. Same shape as prefix sums, just with instead of +.

## Problem

> Given an integer array `nums`, return an array `output` where `output[i]` is the product of all
> the elements of `nums` except `nums[i]`. Each product is guaranteed to fit in a 32-bit integer.
>
> **Follow-up:** Could you solve it in $O(n)$ time **without using the division operation**?

**Example 1**
```
Input:  nums = [1, 2, 4, 6]
Output: [48, 24, 12, 8]
```

**Example 2**
```
Input:  nums = [-1, 0, 1, 2, 3]
Output: [0, -6, 0, 0, 0]
```

**Constraints**
- `2 <= len(nums) <= 10^5`
- `-30 <= nums[i] <= 30`
- The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit integer.

## Thinking

- **Brute force idea:** for each `i`, multiply every other element: $O(n^2)$. Too slow at $n = 10^5$.
- **Division idea:** total product $P$, then `output[i] = P / nums[i]`: $O(n)$. But it breaks on
  zeros (need special cases for 0, 1, or 2+ zeros), and the follow-up forbids division.
- **Key insight:** "everything except `i`" = **everything to the left of `i`** × **everything to
  the right of `i`**:
  $$\text{output}[i] = \underbrace{\textstyle\prod_{j<i} \text{nums}[j]}_{\text{prefix}} \times \underbrace{\textstyle\prod_{j>i} \text{nums}[j]}_{\text{suffix}}$$
  Both are running products, so one left-to-right pass and one right-to-left pass give every
  answer in $O(n)$ with no division. Zeros need no special handling.
- **Space trick:** store the prefix products directly in `output`, then sweep right-to-left
  multiplying in a single running `suffix` variable → $O(1)$ extra space (the output array
  doesn't count).
- **Edge cases to remember:** one zero (only its own position is non-zero), two or more zeros
  (everything is 0), negative numbers, length 2 (`[a, b]` → `[b, a]`).

### Walkthrough of the best solution (Approach C)

**The idea:** for position `i`, "everything except `nums[i]`" splits into two parts:

```
nums = [ a, b, c, d, e ]
               ↑ i = 2
everything except c  =  (a × b)   ×   (d × e)
                         left part    right part
                         = prefix     = suffix
```

**By hand**, for `nums = [1, 2, 4, 6]` ("nothing" counts as **1**, which is why `prefix` and
`suffix` both start at 1):

| i | nums[i] | left of i | prefix | right of i | suffix | prefix × suffix |
|---|---|---|---|---|---|---|
| 0 | 1 | (nothing) | **1** | 2·4·6 | **48** | 48 |
| 1 | 2 | 1 | **1** | 4·6 | **24** | 24 |
| 2 | 4 | 1·2 | **2** | 6 | **6** | 12 |
| 3 | 6 | 1·2·4 | **8** | (nothing) | **1** | 8 |

**Pass 1, left to right:** store the prefix product in `result`.

```python
prefix = 1
for i in range(n):
    result[i] = prefix     # ① store "product of everything LEFT of i"
    prefix *= nums[i]      # ② then include nums[i] for the next position
```

| i | ① result[i] = prefix | ② prefix *= nums[i] | result after |
|---|---|---|---|
| 0 | result[0] = 1 | prefix = 1·1 = 1 | [1, 1, 1, 1] |
| 1 | result[1] = 1 | prefix = 1·2 = 2 | [1, 1, 1, 1] |
| 2 | result[2] = 2 | prefix = 2·4 = 8 | [1, 1, 2, 1] |
| 3 | result[3] = 8 | prefix = 8·6 = 48 | [1, 1, 2, 8] |

**The order of ① and ② is the key detail:** store first, multiply after. When `result[i]` is
written, `prefix` doesn't include `nums[i]` yet, so position `i` is left out. Swap the lines and
every position includes itself.

**Pass 2, right to left:** multiply in the suffix product, kept in one running variable.

```python
suffix = 1
for i in range(n - 1, -1, -1):
    result[i] *= suffix    # ① result[i] = prefix × "product RIGHT of i"
    suffix *= nums[i]      # ② then include nums[i] for the next position (to the left)
```

| i | ① result[i] *= suffix | ② suffix *= nums[i] | result after |
|---|---|---|---|
| 3 | 8 × 1 = **8** | suffix = 1·6 = 6 | [1, 1, 2, 8] |
| 2 | 2 × 6 = **12** | suffix = 6·4 = 24 | [1, 1, 12, 8] |
| 1 | 1 × 24 = **24** | suffix = 24·2 = 48 | [1, 24, 12, 8] |
| 0 | 1 × 48 = **48** | suffix = 48·1 = 48 | [48, 24, 12, 8] ✓ |

**Why one variable instead of a suffix array?** Each suffix value is used once, exactly when the
right-to-left pass reaches that position, so a running variable is enough. The only array is
`result` (the output doesn't count), so extra space is $O(1)$.

**Why zeros need no special case**, for `nums = [-1, 0, 1, 2, 3]`:
- Pass 1 gives `result = [1, -1, 0, 0, 0]`. Once `prefix` passes the 0, it stays 0.
- Pass 2, right to left:
  - i=4: 0 × 1 = 0, then suffix = 3
  - i=3: 0 × 3 = 0, then suffix = 6
  - i=2: 0 × 6 = 0, then suffix = 6
  - i=1: −1 × 6 = **−6**, then suffix = 0
  - i=0: 1 × 0 = 0
- Result `[0, -6, 0, 0, 0]` ✓. The zero's own position skips the zero on both sides, so it
  gets the real product. Every other position picks up the zero from one side. Nothing is
  divided, so nothing special is needed.

**Summary:** answer = left product × right product. In each pass, **use the running product,
then multiply in `nums[i]`**. That order is what leaves `nums[i]` out.

## Solution

### Approach A — my version (total product + division, zero counting)

**Complexity:** Time $O(n)$ · Space $O(1)$ extra. It's correct and the Big-O is already optimal,
but it doesn't answer the question being asked:
1. **It uses division**, which the follow-up rules out. Division is also the fragile part: it
   needs the three zero cases (0, 1, 2+ zeros), and `//` only works because the division is
   always exact (`//` floors, so a non-exact case with negatives would be wrong). In C++/Java
   the full product can also overflow even when every answer fits.
2. **Several passes:** `nums.count(0)`, `math.prod(nums)`, then the division pass; in the
   one-zero case it adds an `enumerate` pass plus a filtered copy of the list. They're mostly
   C-level loops, so it's still quick in Python.
3. Small things: `result` is built before the early return even when unused; `prod != 0` is
   just `zero_count == 0` again; the comprehension reuses the name `num` from the outer loop.

The code is unchanged except for the signature and comments.

```python
import math
from itertools import accumulate
from operator import mul

def product_except_self_mine(nums: list[int]) -> list[int]:
    zero_count = nums.count(0)                       # pass 1
    result = [0 for _ in range(len(nums))]
    if zero_count > 1:
        return result
    prod = math.prod(nums)                           # pass 2

    if prod != 0:                                    # same as zero_count == 0
        return [prod // num for num in nums]         # DIVISION: what the follow-up forbids
    for index, num in enumerate(nums):               # pass 3 (one-zero case only)
        if num == 0:
            new_prod = math.prod([num for num in nums if num != 0])  # copies the list
            result[index] = new_prod
    return result
```

### Approach B — prefix and suffix arrays

**Complexity:** Time $O(n)$ · Space $O(n)$ extra.
`prefix[i]` = product of everything left of `i`, `suffix[i]` = product of everything right of `i`;
the answer is `prefix[i] * suffix[i]`. The easiest version to derive on a whiteboard: write it
first, then optimise the space away (Approach C).

```python
def product_except_self_arrays(nums: list[int]) -> list[int]:
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n
    for i in range(1, n):
        prefix[i] = prefix[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] * nums[i + 1]
    return [p * s for p, s in zip(prefix, suffix)]
```

### Approach C — prefix in the output, running suffix ✅ best practice (interview answer)

**Complexity:** Time $O(n)$ · Space $O(1)$ extra (output not counted).
Pass 1 writes the prefix products into `result`. Pass 2 walks right-to-left keeping the suffix
product in one variable and multiplies it in. No division, no zero cases, two passes.

```python
def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix          # product of nums[:i]
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix         # times product of nums[i+1:]
        suffix *= nums[i]
    return result
```

### Approach D — `itertools.accumulate` (Pythonic)

**Complexity:** Time $O(n)$ · Space $O(n)$ extra.
Same prefix × suffix idea, but the running products are computed in C by `accumulate`.
`initial=1` shifts them by one so `prefix[i]` excludes `nums[i]`. Short, but it uses $O(n)$
extra space and wasn't faster than C in the timing below. Good to know `accumulate`; in an
interview, write C.

```python
def product_except_self_accumulate(nums: list[int]) -> list[int]:
    prefix = list(accumulate(nums, mul, initial=1))            # prefix[i] = prod(nums[:i])
    suffix = list(accumulate(reversed(nums), mul, initial=1))  # suffix[j] = prod of last j
    # output[i] = prefix[i] * suffix[n-1-i]; map/zip stop at the shorter, all in C
    return list(map(mul, prefix, reversed(suffix[:-1])))
```

## Scratch / Experiments

Max size $n = 10^5$. Random values would make the product astronomically large (Python ints
never overflow, so it would measure bigint arithmetic), so to respect the "fits in 32 bits"
constraint the input is mostly $\pm 1$ with a few $2$s. Two inputs: no zeros, and one zero
(the extra-pass branch of Approach A).

Typical results (ms, $n = 10^5$):

| Approach | no zero | one zero |
|---|---|---|
| A mine (division) | ~6 | ~7.4 |
| B prefix + suffix arrays | ~13–17 | ~13 |
| C prefix in output ✅ | ~8 | ~6.7 |
| D `accumulate` | ~10 | ~7 |

All four are $O(n)$, so the gaps are **constant factors**:
- **A is fastest with no zeros** because `count`, `math.prod` and one comprehension are mostly
  C-level work. With one zero it does extra passes and C catches up. Fast, but it skips the
  follow-up, which was the point.
- **B is slowest:** two extra $n$-sized lists plus three Python loops (two index loops and the
  `zip`). C does the same work with no extra arrays.
- **D isn't a free win:** `accumulate`/`map` run in C, but it builds three $n$-sized lists
  (prefix, suffix, the `suffix[:-1]` slice) and every multiplication still creates a Python int,
  so it ends up level with C. "Use the C builtin" only pays off when it removes a lot of Python
  bytecode; here C's loop is already very simple.

```python
import random

random.seed(0)
no_zero = [random.choice([1, -1]) for _ in range(100_000)]
for i in random.sample(range(100_000), 20):
    no_zero[i] = 2
one_zero = list(no_zero)
one_zero[50_000] = 0

for label, nums in [("no zero", no_zero), ("one zero", one_zero)]:
    print(f"--- {label}")
    for fn in APPROACHES:
        print(f"{fn.__name__:32s}", end=" ")
        %timeit fn(nums)
```

## Takeaways

- **Pattern:** "combine everything **except** index `i`" (or "everything left of `i`" /
  "everything right of `i`") → **prefix × suffix**: one pass left-to-right, one pass
  right-to-left. Store one direction in the output and keep the other as a running variable for
  $O(1)$ extra space. Same shape as prefix **sums**, just with `*` instead of `+`.
- **Mistakes I made:**
  - Reached for **division** to "undo" one element. Inverting an operation needs special cases
    (here: zeros, and exact vs floor division with negatives) and is often banned or impossible
    (`max`, `gcd`, overflow in fixed-width ints). Prefix/suffix needs no inverse at all.
  - Didn't treat the follow-up as the real question: "$O(n)$ without division" was the point of
    the problem.
  - Small hygiene: built `result` before an early return that didn't need it, checked the same
    condition twice (`zero_count` and `prod != 0`), and reused `num` inside a comprehension.
- **Related problems:** Range Sum Query – Immutable (#303, prefix sums), Trapping Rain Water
  (#42, prefix max from the left vs suffix max from the right), Maximum Product Subarray (#152,
  running products with negatives), Subarray Sum Equals K (#560, prefix sums + hash map),
  Find Pivot Index (#724, left sum vs right sum).

---

From https://taosu.blog/notes/0238-product-of-array-except-self