# NEETCODE - Arrays and Hashing: Products of Array Except Self

Array manipulation without division - From O(n²) nested loops to O(n) prefix-suffix pattern

Technology: **Python, Algorithms**  
Skill: **Array Traversal, O(n) Space**

## Problem Statement

Given an integer array `nums`, return an array `output` where `output[i]` is the product of all the elements of `nums` except `nums[i]`.

**Examples:**

```python
Input: nums = [1,2,4,6]
Output: [48,24,12,8]
Explanation:
- output[0] = 2*4*6 = 48
- output[1] = 1*4*6 = 24
- output[2] = 1*2*6 = 12
- output[3] = 1*2*4 = 8

Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]
Explanation:
- output[0] = 0*1*2*3 = 0
- output[1] = (-1)*1*2*3 = -6
- output[2] = (-1)*0*2*3 = 0
- output[3] = (-1)*0*1*3 = 0
- output[4] = (-1)*0*1*2 = 0
```

**Constraints:**

- 2 <= nums.length <= 1000
- -20 <= nums[i] <= 20
- Each product is guaranteed to fit in a 32-bit integer
- **Follow-up:** Could you solve it in O(n) time without using division?

**Edge Cases:**

- Array with zeros (single or multiple)
- Array with negative numbers
- Array with all same values
- Minimum size array (length 2)

## Solutions Progression

### Approach 1: Brute Force with Nested Loops (O(n²))

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

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

return output
```

**Time Complexity:** O(n²)  
**Space Complexity:** O(1) excluding output array

### Approach 2: Division with Edge Case Handling (O(n))

```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        zero_count = 0
        product_without_zeros = 1

for num in nums:
            if num == 0:
                zero_count += 1
            else:
                product_without_zeros *= num

output = []
        for num in nums:
            if zero_count > 1:
                output.append(0)
            elif zero_count == 1:
                output.append(product_without_zeros if num == 0 else 0)
            else:
                output.append(product_without_zeros // num)

return output
```

**Time Complexity:** O(n)  
**Space Complexity:** O(1) excluding output

### Approach 3: Prefix and Suffix Products (Optimal - Two Arrays)

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

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

suffix = [1] * n
        for i in range(n-2, -1, -1):
            suffix[i] = suffix[i+1] * nums[i+1]

output = [prefix[i] * suffix[i] for i in range(n)]

return output
```

**Time Complexity:** O(n)  
**Space Complexity:** O(n)

### Approach 4: Space-Optimized Prefix-Suffix (Optimal - O(1) Space)

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

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

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

return output
```

**Time Complexity:** O(n)  
**Space Complexity:** O(1)

## Pattern Recognition

### Core Pattern: Prefix-Suffix Decomposition

This problem exemplifies a fundamental array pattern: **decomposing a computation into prefix and suffix components**.

```python
product_except_self[i] = product(nums[0...i-1]) * product(nums[i+1...n-1])
                       = prefix[i] * suffix[i]
```

## Real-World Applications

1. **Financial Risk Modeling** - Portfolio variance calculations excluding specific assets
2. **Image Processing (Convolutions)** - Computing filter responses with missing pixels
3. **Machine Learning (Leave-One-Out Cross-Validation)** - Training models excluding each sample
4. **Database Query Optimization** - Selectivity estimation for join ordering
5. **Network Traffic Analysis** - Calculating bandwidth excluding specific flows

## Common Mistakes

1. **Forgetting zero handling** - Multiple zeros make all products zero
2. **Integer overflow** - Consider using long or BigInteger types
3. **Off-by-one errors in prefix/suffix**
4. **Not considering negative numbers**
5. **Inefficient space usage** - Creating both prefix and suffix arrays when one suffices

## Complexity Summary Table

| Approach         | Time Complexity | Space Complexity | Use Case                           |
|------------------|----------------|------------------|-------------------------------------|
| Brute Force      | O(n²)         | O(1)             | Small arrays, debugging              |
| Division         | O(n)          | O(1)             | When division is allowed             |
| Two Arrays       | O(n)          | O(n)             | Clean, readable implementation       |
| Optimized        | O(n)          | O(1)             | Production, space-critical            |