Table of contents
Open Table of contents
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]
.
The product of any prefix or suffix of nums
is guaranteed to fit in a 32bit 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 <= 10^5
30 <= nums[i] <= 30
 The product of any prefix or suffix of
nums
is guaranteed to fit in a 32bit integer.
Followup: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
Explanation/Approach
This problem requires calculating the product of all elements in the array except the current one, without using division. A key insight is to use prefix and suffix products.
 Prefix and Suffix Product Arrays: We can create two arrays: one to store the product of all elements to the left of each index, and another for products to the right. Then, for each index, we multiply the corresponding left and right products to get the result.
 Space Optimized Approach: This approach optimizes the previous method by using the output array for one of the product arrays and a variable for the other, thereby achieving O(1) extra space.
Solution 1: Prefix and Suffix Product Arrays
class Solution:
def productExceptSelf(self, nums: List[int]) > List[int]:
length = len(nums)
# Arrays to hold the prefix and suffix products
left_products = [1] * length
right_products = [1] * length
answer = [0] * length
# Calculate left products
for i in range(1, length):
left_products[i] = nums[i  1] * left_products[i  1]
# Calculate right products
for i in reversed(range(length  1)):
right_products[i] = nums[i + 1] * right_products[i + 1]
# Calculate the answer array
for i in range(length):
answer[i] = left_products[i] * right_products[i]
return answer
Time and Memory Complexity
The time complexity is O(n) as it requires traversing the array three times. The space complexity is O(n) for the two additional arrays.
Explanation
We use two extra arrays to store the left and right products for each index. The final answer for each index is then the product of its corresponding left and right values.
Solution 2: Space Optimized Approach
class Solution:
def productExceptSelf(self, nums: List[int]) > List[int]:
length = len(nums)
answer = [0] * length
# Calculate left products and store them in answer
answer[0] = 1
for i in range(1, length):
answer[i] = nums[i  1] * answer[i  1]
# Calculate right products and accumulate in answer
right_product = 1
for i in reversed(range(length)):
answer[i] = answer[i] * right_product
right_product *= nums[i]
return answer
Time and Memory Complexity
The time complexity remains O(n) for traversing the array twice. The space complexity is improved to O(1), as it only uses the answer array and a single variable for the right products.
Explanation
This solution first calculates the left products directly into the answer array. Then, it traverses the array from the end, multiplying each element in the answer array by the running product of elements to the right. This method effectively combines the two steps of the previous solution, thereby saving space.
Visualization:
Imagine the input array nums
is [2, 3, 4, 5]
. The process would look like this:

Initial State:
nums: [2, 3, 4, 5] answer: [0, 0, 0, 0]

After Calculating Left Products:
nums: [2, 3, 4, 5] answer: [1, 2, 6, 24] # [1, 2, 2*3, 2*3*4]

Calculating Right Products:
 Iteration starts from the end.
 Update the
answer
array by multiplying each element byright_product
and updateright_product
.
# First iteration (i = 3) right_product = 1 answer: [1, 2, 6, 24] > [1, 2, 6, 24*1] # Second iteration (i = 2) right_product = 5 answer: [1, 2, 6, 24] > [1, 2, 6*5, 24] # Third iteration (i = 1) right_product = 20 (5*4) answer: [1, 2, 30, 24] > [1, 2*20, 30, 24] # Fourth iteration (i = 0) right_product = 60 (20*3) answer: [1, 40, 30, 24] > [1*60, 40, 30, 24]

Final Result:
nums: [2, 3, 4, 5] answer: [60, 40, 30, 24]