# Product of Array Except Self

- **Canonical ID**: `product-of-array-except-self`
- **Canonical URL**: https://dsacheatsheet.com/problems/product-of-array-except-self
- **Difficulty**: medium
- **Patterns**: Arrays & Hashing
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/product-of-array-except-self/

## 1. Core Invariant / The Trick

Compute prefix products left-to-right directly into `res[i]`, then sweep right-to-left maintaining a running scalar `suffix` product and multiply `res[i] *= suffix`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Two linear passes reuse the output array for prefix storage and a single scalar for suffix products, achieving O(1) extra space without division.

## 3. Minimal Idiomatic Code

### Python
```python
def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [1] * n
    prefix = 1
    for i in range(n):
        res[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= suffix
        suffix *= nums[i]
    return res
```

### TypeScript
```typescript
export function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const res = new Array(n).fill(1);
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    res[i] = prefix;
    prefix *= nums[i];
  }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    res[i] *= suffix;
    suffix *= nums[i];
  }
  return res;
}
```

### C++
```cpp
vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size(), pre = 1, suf = 1;
    vector<int> res(n, 1);
    for (int i = 0; i < n; ++i) { res[i] = pre; pre *= nums[i]; }
    for (int i = n - 1; i >= 0; --i) { res[i] *= suf; suf *= nums[i]; }
    return res;
}
```

### Java
```java
int[] productExceptSelf(int[] nums) {
    int n = nums.length, pre = 1, suf = 1;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) { res[i] = pre; pre *= nums[i]; }
    for (int i = n - 1; i >= 0; i--) { res[i] *= suf; suf *= nums[i]; }
    return res;
}
```

### Go
```go
func productExceptSelf(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    pre, suf := 1, 1
    for i := 0; i < n; i++ { res[i] = pre; pre *= nums[i] }
    for i := n - 1; i >= 0; i-- { res[i] *= suf; suf *= nums[i] }
    return res
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Using total product divided by `nums[i]` crashes on zeros and violates the division constraint.

### Follow-ups
- Counting zeros fixes division only if division were allowed; prefix-suffix works uniformly in rings without division.