LeetEye LeetEye
Easy Prefix/Suffix Arrays ~5 min

Product of Array Except Self

arrays-and-hashing product-of-array-except-self

Problem

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].

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

Examples

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]
Key Insight

Product of all except nums[i] = (product of everything left of i) × (product of everything right of i)

Product except self = prefix product × suffix product. Compute in two passes.

How to Approach This Problem

Pattern Recognition: When you see keywords like product of array except self arrays-and-hashing, think Prefix/Suffix Arrays.

Step-by-Step Reasoning

1 If division were allowed, the solution would be:
Answer: Compute total product, divide by each element
Total product / nums[i] = product of all others. But the problem forbids division, likely to handle zeros properly (division by zero) or as a learning exercise.
2 Product of all elements except nums[i] equals:
Answer: (Product of elements before i) × (Product of elements after i)
This decomposition avoids needing nums[i] itself. We multiply everything to the left with everything to the right.
3 prefix[i] represents:
Answer: nums[0] × nums[1] × ... × nums[i-1]
Prefix product at i is the product of all elements BEFORE index i (exclusive of i).
4 suffix[i] represents:
Answer: nums[i+1] × nums[i+2] × ... × nums[n-1]
Suffix product at i is the product of all elements AFTER index i (exclusive of i).
5 The answer for position i is:
Answer: prefix[i] × suffix[i]
Product of everything before × product of everything after = product of everything except nums[i].
6 We can reduce from O(n) extra space to O(1) by:
Answer: Computing prefix in result array, then multiplying suffix on second pass
First pass: fill result with prefix products. Second pass: multiply each result[i] by running suffix product. We only need a single variable for the running suffix.

Solution

def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [1] * n
    
    # First pass: compute prefix products
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    
    # Second pass: multiply by suffix products
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Prefix/Suffix Arrays problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye