Product of Array Except Self

Problem Statement

Return an array output such that output[i] is the product of all elements of nums except nums[i].

Example: nums = [1,2,3,4] ā†’ Output: [24,12,8,6]

Approach 1: Brute Force

Explanation: Multiply all elements except current for each index.

Time Complexity: O(nĀ²)

Space Complexity: O(1) or O(n) for output

for i in 0..n-1:
    prod=1
    for j in 0..n-1:
        if i != j:
            prod *= nums[j]
    output[i]=prod

Approach 2: Prefix & Suffix Arrays

Explanation: Compute prefix and suffix products separately.

Time Complexity: O(n)

Space Complexity: O(n)

prefix[0]=1
for i in 1..n-1:
    prefix[i]=prefix[i-1]*nums[i-1]
suffix[n-1]=1
for i in n-2..0:
    suffix[i]=suffix[i+1]*nums[i+1]
for i in 0..n-1:
    output[i]=prefix[i]*suffix[i]

Approach 3: Optimal (No extra arrays)

Explanation: Use output array as prefix, then multiply suffix on the go.

Time Complexity: O(n)

Space Complexity: O(1) ignoring output array

output[0]=1
for i in 1..n-1:
    output[i]=output[i-1]*nums[i-1]
suffix=1
for i in n-1..0:
    output[i] *= suffix
    suffix *= nums[i]