One of the most asked questions on LeetCode and an important problem pattern. The optimal solution uses a modification of the prefix sum approach. Division is not allowed.
Problem Statement
Given an array nums of n integers, return an array output such that output[i] is equal to
the product of all elements of nums except nums[i].
Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Solutions
1. Brute Force — O(N²) time, O(1) space
For each index, compute the product of all other elements.
def productExceptSelf(nums):
n = len(nums)
result = [0] * n
for i in range(n):
product = 1
for j in range(n):
if i != j:
product = product * nums[j]
result[i] = product
return result
2. Prefix + Postfix Arrays — O(N) time, O(N) space
Precompute a left-product array (product of everything left of index i) and a right-product array
(product of everything right of index i). The answer for each index is left[i] * right[i].
index: 0 1 2 3
nums: 1 2 3 4
left_prod: 1 1 2 6 ← product of everything LEFT of i
right_prod: 24 12 4 1 ← product of everything RIGHT of i
result: 24 12 8 6
def productExceptSelf(nums):
n = len(nums)
left_prod = [1] * n
right_prod = [1] * n
result = [1] * n
for i in range(1, n):
left_prod[i] = left_prod[i-1] * nums[i-1]
for i in range(n-2, -1, -1):
right_prod[i] = right_prod[i+1] * nums[i+1]
for i in range(n):
result[i] = left_prod[i] * right_prod[i]
return result
3. Optimal — O(N) time, O(1) space
Avoid the extra arrays. First pass: fill result with left products. Second pass: multiply in the
right product using a running variable.
def productExceptSelf(nums):
n = len(nums)
result = [1] * n
for i in range(1, n):
result[i] = result[i-1] * nums[i-1]
r_prod = 1
for i in range(n-1, -1, -1):
result[i] = r_prod * result[i]
r_prod *= nums[i]
return result
O(N) time, O(1) extra space. Two passes, no division, no extra arrays.
Best of luck. Later.