# LeetCode 238: Product of Array Except Self

## Problem Restatement

We are given an integer array `nums`.

We need to return an array `answer` where:

```text
answer[i] = product of all nums[j] where j != i
```

We must solve it:

- In `O(n)` time
- Without using division

LeetCode gives this example:

```text
Input:  nums = [1,2,3,4]
Output: [24,12,8,6]
```

The product of any prefix or suffix is guaranteed to fit in a 32-bit integer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Array `answer` of the same length |
| Rule | `answer[i]` is the product of every value except `nums[i]` |
| Constraint | Do not use division |
| Target time | `O(n)` |

Function shape:

```python
class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        ...
```

## Examples

Example 1:

```text
Input:  nums = [1,2,3,4]
Output: [24,12,8,6]
```

For each index:

```text
answer[0] = 2 * 3 * 4 = 24
answer[1] = 1 * 3 * 4 = 12
answer[2] = 1 * 2 * 4 = 8
answer[3] = 1 * 2 * 3 = 6
```

Example 2:

```text
Input:  nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
```

Only index `2` gets a non-zero result, because `nums[2]` is the zero. Every other index still includes that zero in its product.

## First Thought: Brute Force

For each index `i`, we can multiply every element except `nums[i]`.

```python
class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = []

        for i in range(n):
            product = 1

            for j in range(n):
                if i != j:
                    product *= nums[j]

            ans.append(product)

        return ans
```

This is correct, but it is too slow.

For each of `n` positions, we scan `n` values.

So the time complexity is:

```text
O(n^2)
```

We need a linear solution.

## Key Insight

For each index `i`, the product except self can be split into two parts:

```text
product of everything left of i
*
product of everything right of i
```

For:

```text
nums = [1, 2, 3, 4]
```

At index `2`, the value is `3`.

The product except self is:

```text
left side:  1 * 2
right side: 4

answer[2] = (1 * 2) * 4 = 8
```

So we do not need division.

We only need prefix products and suffix products.

## Prefix and Suffix Products

A prefix product before index `i` means:

```text
nums[0] * nums[1] * ... * nums[i - 1]
```

A suffix product after index `i` means:

```text
nums[i + 1] * nums[i + 2] * ... * nums[n - 1]
```

Then:

```text
answer[i] = prefix_before_i * suffix_after_i
```

For `nums = [1,2,3,4]`:

| Index | Value | Left Product | Right Product | Answer |
|---|---:|---:|---:|---:|
| `0` | `1` | `1` | `2*3*4 = 24` | `24` |
| `1` | `2` | `1` | `3*4 = 12` | `12` |
| `2` | `3` | `1*2 = 2` | `4` | `8` |
| `3` | `4` | `1*2*3 = 6` | `1` | `6` |

The empty product is `1`.

That is why the left product of the first element is `1`, and the right product of the last element is `1`.

## Algorithm

We can store left products directly in the output array.

First pass, left to right:

1. Start `left = 1`.
2. For each index `i`:
   - Set `ans[i] = left`.
   - Update `left *= nums[i]`.

After this pass, `ans[i]` contains the product of all numbers to the left of `i`.

Second pass, right to left:

1. Start `right = 1`.
2. For each index `i` from right to left:
   - Multiply `ans[i] *= right`.
   - Update `right *= nums[i]`.

After this pass, each `ans[i]` has:

```text
left product * right product
```

which is exactly the product of all values except `nums[i]`.

## Walkthrough

Use:

```text
nums = [1, 2, 3, 4]
```

Start:

```text
ans = [1, 1, 1, 1]
left = 1
```

First pass:

| `i` | `nums[i]` | `ans[i] = left` | New `left` |
|---:|---:|---:|---:|
| `0` | `1` | `1` | `1` |
| `1` | `2` | `1` | `2` |
| `2` | `3` | `2` | `6` |
| `3` | `4` | `6` | `24` |

Now:

```text
ans = [1, 1, 2, 6]
```

Second pass:

```text
right = 1
```

| `i` | `nums[i]` | `ans[i] *= right` | New `right` |
|---:|---:|---:|---:|
| `3` | `4` | `6 * 1 = 6` | `4` |
| `2` | `3` | `2 * 4 = 8` | `12` |
| `1` | `2` | `1 * 12 = 12` | `24` |
| `0` | `1` | `1 * 24 = 24` | `24` |

Final result:

```text
[24, 12, 8, 6]
```

## Correctness

For each index `i`, after the first pass, `ans[i]` equals the product of all elements before `i`.

This is true because `left` starts at `1`, and before processing index `i`, it contains exactly:

```text
nums[0] * nums[1] * ... * nums[i - 1]
```

Then the second pass scans from right to left.

Before processing index `i`, `right` contains exactly:

```text
nums[i + 1] * nums[i + 2] * ... * nums[n - 1]
```

The algorithm multiplies:

```python
ans[i] *= right
```

So `ans[i]` becomes:

```text
product of all elements before i
*
product of all elements after i
```

This is exactly the product of all elements except `nums[i]`.

Since this happens for every index, the algorithm returns the correct array.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Two linear scans |
| Extra space | `O(1)` | Only `left` and `right`, excluding the output array |

The output array is required by the problem, so it is usually not counted as extra space.

## Implementation

```python
class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [1] * n

        left = 1
        for i in range(n):
            ans[i] = left
            left *= nums[i]

        right = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= right
            right *= nums[i]

        return ans
```

## Code Explanation

Create the output array:

```python
ans = [1] * n
```

Then compute products to the left:

```python
left = 1
for i in range(n):
    ans[i] = left
    left *= nums[i]
```

At index `i`, `left` does not include `nums[i]` yet. That is why it correctly represents the product of elements before `i`.

Then compute products to the right:

```python
right = 1
for i in range(n - 1, -1, -1):
    ans[i] *= right
    right *= nums[i]
```

At index `i`, `right` does not include `nums[i]` yet. That is why it correctly represents the product of elements after `i`.

Finally:

```python
return ans
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.productExceptSelf([1, 2, 3, 4]) == [24, 12, 8, 6]
    assert s.productExceptSelf([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
    assert s.productExceptSelf([2, 3]) == [3, 2]
    assert s.productExceptSelf([0, 0]) == [0, 0]
    assert s.productExceptSelf([5, 0, 2]) == [0, 10, 0]
    assert s.productExceptSelf([-1, -2, -3, -4]) == [-24, -12, -8, -6]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,2,3,4]` | Standard example |
| `[-1,1,0,-3,3]` | Contains one zero |
| `[2,3]` | Minimum useful length |
| `[0,0]` | Multiple zeros |
| `[5,0,2]` | Single zero in middle |
| Negative values | Checks sign handling |