Product of Array Except Self

Difficulty: Medium
Topics: Array, Prefix Sum
Link: https://leetcode.com/problems/product-of-array-except-self/

Problem Description

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

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

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

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

Example 2:

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

Constraints:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Solution

1. Problem Deconstruction

Technical Restatement
Given an array nums of length n, construct an array answer where each answer[i] equals the product of all elements in nums except nums[i]. Constraints:

Time: O(n)
Space: O(1) (excluding output)
Division prohibited

Beginner-Friendly Restatement
For every number in the input list, create a new list where each position contains the multiplication of all other numbers except the one at that position. Do this efficiently without division.

Mathematical Formulation
Given array nums, compute answer such that:

answer[i] = \prod_{j=0}^{i-1} nums[j] \times \prod_{j=i+1}^{n-1} nums[j]

Constraint Analysis

Length 2 ≤ n ≤ 1e5:
- Limitation: Rules out brute-force O(n²) approaches.
- Edge Case: Small n (e.g., n=2) requires careful index handling.
Values -30 ≤ nums[i] ≤ 30:
- Limitation: Zero and negative values complicate product tracking.
- Edge Case: Multiple zeros make all products zero except positions with zeros.
No division:
- Limitation: Prevents trivial total-product/current-element solutions.

2. Intuition Scaffolding

Real-World Analogy
Imagine a relay race where each runner’s contribution is replaced by the product of all other runners’ speeds. To compute this efficiently, track cumulative speed before and after each runner.

Gaming Analogy
Like crafting a weapon by combining all available gems except one. Track gems collected (prefix) and remaining gems (suffix) to avoid recalculating totals.

Math Analogy
Decompose the problem into left/right partial products, akin to splitting a matrix multiplication into row and column vectors.

Common Pitfalls

Dividing by zero: Invalid when nums[i] = 0.
Nested loops: Results in O(n²) time.
Overflow assumptions: While products fit in 32-bit, intermediates could exceed if not tracked properly.
Misindexing prefix/suffix: Off-by-one errors during accumulation.
Ignoring space constraints: Storing separate prefix/suffix arrays when unnecessary.

3. Approach Encyclopedia

Brute Force

def brute_force(nums):  
    n = len(nums)  
    answer = [1] * n  
    for i in range(n):  
        for j in range(n):  
            if i != j:  
                answer[i] *= nums[j]  
    return answer

Time: O(n²)
Space: O(1) (excluding output)

Optimal Two-Pass (Prefix/Suffix)

def optimal_two_pass(nums):  
    n = len(nums)  
    prefix = [1] * n  
    suffix = [1] * n  
    answer = [1] * n  
    # Compute prefix  
    for i in range(1, n):  
        prefix[i] = prefix[i-1] * nums[i-1]  
    # Compute suffix  
    for i in range(n-2, -1, -1):  
        suffix[i] = suffix[i+1] * nums[i+1]  
    # Combine  
    for i in range(n):  
        answer[i] = prefix[i] * suffix[i]  
    return answer

Time: O(n) (3 passes)
Space: O(n) (2 auxiliary arrays)

Space-Optimized One-Pass

def productExceptSelf(nums):  
    n = len(nums)  
    answer = [1] * n  
    # Prefix pass (left to right)  
    for i in range(1, n):  
        answer[i] = answer[i-1] * nums[i-1]  
    # Suffix integration (right to left)  
    right_prod = 1  
    for i in range(n-1, -1, -1):  
        answer[i] *= right_prod  
        right_prod *= nums[i]  
    return answer

Time: O(n) (2 passes)
Space: O(1) (excluding output)

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

Prefix Pass: [1, 1, 2, 6]  
Suffix Integration:  
Initial right_prod=1  
i=3 → answer[3]=6*1=6, right_prod=4  
i=2 → answer[2]=2*4=8, right_prod=12  
i=1 → answer[1]=1*12=12, right_prod=24  
i=0 → answer[0]=1*24=24, right_prod=24  
Final answer: [24,12,8,6]

4. Code Deep Dive

Line-by-Line Explanation

def productExceptSelf(nums):  
    n = len(nums)  
    answer = [1] * n  # Initialize output with multiplicative identity  
    # Prefix pass: answer[i] = product(nums[0..i-1])  
    for i in range(1, n):  
        answer[i] = answer[i-1] * nums[i-1]  # Cumulative product  
    # Suffix pass: multiply by product(nums[i+1..n-1])  
    right_prod = 1  # Tracks product of elements to the right  
    for i in range(n-1, -1, -1):  
        answer[i] *= right_prod  # Combine prefix and suffix  
        right_prod *= nums[i]  # Update right product for next iteration  
    return answer

Edge Case Handling

Example 2 (nums = [-1,1,0,-3,3]):
- After prefix pass: [1, -1, -1, 0, 0]
- Suffix pass:
  - i=4: answer[4] = 0*1 = 0; right_prod = 3
  - i=3: answer[3] = 0*3 = 0; right_prod = -9
  - i=2: answer[2] = -1*-9 = 9; right_prod = 0
  - Result: [0,0,9,0,0]

5. Complexity War Room

Hardware-Aware Analysis

For n=1e5, the output array consumes 4e5 bytes ≈ 400KB, fitting in CPU cache (L3 typically 2-30MB).
Two linear passes minimize cache misses.

Industry Approach Comparison

Approach	Time	Space (Extra)	Readability	Interview Viability
Brute Force	O(n²)	O(1)	9/10	❌
Two-Pass	O(n)	O(n)	8/10	✅
Optimized	O(n)	O(1)	7/10	✅

6. Pro Mode Extras

Variants

Product with Division:
- Compute total product, handle zeros separately.
Two Transactions (LC 123):
- Extend to track prefix/suffix maxima for buy/sell points.

Interview Cheat Sheet

First Mention: Always state time/space complexity upfront.
Key Insight: “We can decompose the problem into left/right products and reuse the output array for space optimization.”
Common Gotcha: “Handling zeros requires careful tracking but doesn’t require special cases in this approach.”

#238 - Product of Array Except Self