This problem looks simple to solve in linear time and space. This problem builds on some of the fundamental concepts of arrays.
 Array traversals.
 Prefix and Suffix sum.
Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe, and many more top tech companies.
Problem statement
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.
Test case#1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Test case#2:
Input: nums = [1,1,0,3,3]
Output: [0,0,9,0,0]
Understanding the problem
This problem looks simpler to solve in linear time and space, but it is tricky when writing the pseudocode or actual code implementation.
Illustration
Let us see what the results that are expected from a simple array containing 4 elements:
input = {1, 2, 3, 4}
So, the value at each index is the product of all the other elements in the array except the value itself. The following figure illustrates this.
Based on the above figure, we can come up with a formula. For any given index i
, we can find the value using the product of the elements from o
to (i  1)
plus product of elements from (i + 1)
to (N  1)
. This is illustrated in the following figure:
Thought process
Before writing pseudo code, come up with questions and ask the interviewer.
 Should I be worried about duplicates?
 What if the array is empty or has a single element? What are the expected results?
 Should I consider/ignore
0
value in any of the indexes in the array? because all other values get0
except the index containing0
.  What are the corner/edge cases for this problem?
Once you and the interviewer have discussed the above questions, devise various approaches to solving the problem.
 Naive approach/bruteforce.
 Product of all elements.
 Left and Right products.
 Prefix and suffix sums.
Approach 1: Naive/Bruteforce
Intuition
To employ the brute force approach, we must execute two forloops. When the outer loop index matches the inner loop index value, we should skip the product; otherwise, we proceed with the product.
Algorithm
 Initialize Variables:

N = nums.length
(length of the input array). 
result = new int[N]
(array to store the results).

 Outer Loop (Iterate through each element in
nums
): For i = 0 to N1:Initialize currentProduct = 1.
 Inner Loop (Calculate product for current element), for
j = 0
toN1
: If
i == j
, skip the current iteration using continue.  Multiply
currentProduct
bynums[j]
.  Assign
currentProduct
toresult[i]
.
 If
 Return
result
.
Code
// brute force
static int[] bruteForce(int[] nums) {
int N = nums.length;
int[] result = new int[N];
for (int i = 0; i < N; i++) {
int currentProduct = 1;
for (int j = 0; j < N; j++) {
if (i == j) {
continue;
}
currentProduct *= nums[j];
}
result[i] = currentProduct;
}
return result;
}
Complexity analysis

Time complexity:
O(n^2)
, for iterating the array twice in outer and inner loops. 
Space complexity:
O(n)
, for the auxiliary space (result[] array) we used.
Approach 2: Product of array ❌
One way most developers think is to run a product sum of all elements, divide the product sum by each array value, and return the result.
Pseudocode
// O(n) time and O(1) space
p = 1
for i > 0 to A[i]
p * = A[i]
for i > 0 to (N  1)
A[i] = p/A[i] // if A[i] == 0 🤔 BAM error‼️
Code
// code implementation
static int[] productSum(int[] nums) {
int product_sum = 1;
for(int num: nums) {
product_sum *= num;
}
for(int i = 0; i < nums.length; i++) {
nums[i] = product_sum/nums[i];
}
return nums;
}
What if one of the array elements contain 0
? 🤔
The value at all the indexes except the index containing 0
will definitely be infinity
. Also, the code throws java.lang.ArithmeticException
.
Exception in thread "main" java.lang.ArithmeticException: / by zero
at dev.ggorantala.ds.arrays.ProductOfArrayItself.productSum(ProductOfArrayItself.java:24)
at dev.ggorantala.ds.arrays.ProductOfArrayItself.main(ProductOfArrayItself.java:14)
Approach 3: Find Prefix and Suffix product
Learn more about prefix and suffix sum in the Arrays Mastery Course on my website https://ggorantala.dev
Intuition & formulae's
Prefix and Suffix are calculated before writing an algorithm for the result. Prefix and Suffix sum formulae are given below:
Algorithm Steps
 Create an array
result
of the same length asnums
to store the final results.  Create two additional arrays
prefix_sum
andsuffix_sum
of the same length asnums
.  Calculate Prefix Products:
 Set the first element of
prefix_sum
to the first element ofnums
.  Iterate through the input array
nums
starting from the second element (index 1). For each indexi
, setprefix_sum[i]
to the product ofprefix_sum[i1]
andnums[i]
.
 Set the first element of
 Calculate Suffix Products:
 Set the last element of
suffix_sum
to the last element ofnums
.  Iterate through the input array
nums
starting from the secondtolast element (indexnums.length  2
) to the first element. For each indexi
, setsuffix_sum[i]
to the product ofsuffix_sum[i+1]
andnums[i]
.
 Set the last element of
 Calculate the result: Iterate through the input array nums.
 For the first element
(i == 0)
, setresult[i]
tosuffix_sum[i + 1]
.  For the last element
(i == nums.length  1)
, setresult[i]
toprefix_sum[i  1]
.  For all other elements, set
result[i]
to the product ofprefix_sum[i  1]
andsuffix_sum[i + 1]
.
 For the first element
 Return the result array containing the product of all elements except the current element for each index.
Pseudocode
Function usingPrefixSuffix(nums):
N = length of nums
result = new array of length N
prefix_sum = new array of length N
suffix_sum = new array of length N
// Calculate prefix products
prefix_sum[0] = nums[0]
For i from 1 to N1:
prefix_sum[i] = prefix_sum[i1] * nums[i]
// Calculate suffix products
suffix_sum[N1] = nums[N1]
For i from N2 to 0:
suffix_sum[i] = suffix_sum[i+1] * nums[i]
// Calculate result array
For i from 0 to N1:
If i == 0:
result[i] = suffix_sum[i+1]
Else If i == N1:
result[i] = prefix_sum[i1]
Else:
result[i] = prefix_sum[i1] * suffix_sum[i+1]
Return result
Code
// using prefix and suffix arrays
private static int[] usingPrefixSuffix(int[] nums) {
int[] result = new int[nums.length];
int[] prefix_sum = new int[nums.length];
int[] suffix_sum = new int[nums.length];
// prefix sum calculation
prefix_sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
prefix_sum[i] = prefix_sum[i  1] * nums[i];
}
// suffix sum calculation
suffix_sum[nums.length  1] = nums[nums.length  1];
for (int i = nums.length  2; i >= 0; i) {
suffix_sum[i] = suffix_sum[i + 1] * nums[i];
}
for (int i = 0; i < nums.length; i++) {
if (i == 0) { // when variable `i` is at 0th index
result[i] = suffix_sum[i + 1];
} else if (i == nums.length  1) { // when variable `i` is at last index
result[i] = prefix_sum[i  1];
} else { // for all other indexes
result[i] = prefix_sum[i  1] * suffix_sum[i + 1];
}
}
return result;
}
Complexity analysis

Time complexity: The time complexity of the given code is
O(n)
, wheren
is the length of the input array nums. This is because: Calculating the
prefix_sum
products takeO(n)
time.  Calculating the
suffix_sum
products takeO(n)
time.  Constructing the
result
array takesO(n)
time.
 Calculating the
Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n)
= 3O(n)
, which is O(n)
.

Space complexity: The space complexity of the given code is O(n). This is because:
 The
prefix_sum
array requiresO(n)
space.  The
suffix_sum
array requiresO(n)
space.  The
result
array requiresO(n)
space. All three arrays are of length n, so the total space complexity isO(n) + O(n) + O(n)
=3O(n)
, which isO(n)
.
 The
Optimization 🤩
For the suffix array calculation, we override the input nums
array instead of creating one.
private static int[] usingPrefixSuffixOptimization(int[] nums) {
int[] result = new int[nums.length];
int[] prefix_sum = new int[nums.length];
// prefix sum calculation
prefix_sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
prefix_sum[i] = prefix_sum[i  1] * nums[i];
}
// suffix sum calculation, inplace  `nums` array override
for (int i = nums.length  2; i >= 0; i) {
nums[i] = nums[i + 1] * nums[i];
}
for (int i = 0; i < nums.length; i++) {
if (i == 0) { // when variable `i` is at 0th index
result[i] = nums[i + 1];
} else if (i == nums.length  1) { // when variable `i` is at last index
result[i] = prefix_sum[i  1];
} else { // for all other indexes
result[i] = prefix_sum[i  1] * nums[i + 1];
}
}
return result;
}
Hence, we reduced the space of O(n)
. Time and space are not reduced, but we did a small optimization here.
Approach 4: Using Prefix and Suffix product knowledge 🧐
Intuition
This is a rather easy approach when we use the knowledge of prefix and suffix arrays.
For every given index i
, we will calculate the product of all the numbers to the left and then multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index i
. Let's look at a formal algorithm that describes this idea more clearly.
Algorithm steps
 Create an array
result
of the same length asnums
to store the final results.  Create two additional arrays
prefix_sum
andsuffix_sum
of the same length asnums
.  Calculate Prefix Products:
 Set the first element of
prefix_sum
to1
.  Iterate through the input array nums starting from the second element (index 1). For each index
i
, setprefix_sum[i]
to the product ofprefix_sum[i  1]
andnums[i  1]
.
 Set the first element of
 Calculate Suffix Products:
 Set the last element of
suffix_sum
to1
.  Iterate through the input array nums starting from the secondtolast element (index
nums.length  2
) to the first element.  For each index
i
, setsuffix_sum[i]
to the product ofsuffix_sum[i + 1]
andnums[i + 1]
.
 Set the last element of
 Iterate through the input array
nums
. For each index
i
, setresult[i]
to the product ofprefix_sum[i]
andsuffix_sum[i]
.
 For each index
 Return the
result
array containing the product of all elements except the current element for each index.
Pseudocode
Function prefixSuffix1(nums):
N = length of nums
result = new array of length N
prefix_sum = new array of length N
suffix_sum = new array of length N
// Calculate prefix products
prefix_sum[0] = 1
For i from 1 to N1:
prefix_sum[i] = prefix_sum[i1] * nums[i1]
// Calculate suffix products
suffix_sum[N1] = 1
For i from N2 to 0:
suffix_sum[i] = suffix_sum[i+1] * nums[i+1]
// Calculate result array
For i from 0 to N1:
result[i] = prefix_sum[i] * suffix_sum[i]
Return result
Code
private static int[] prefixSuffixProducts(int[] nums) {
int[] result = new int[nums.length];
int[] prefix_sum = new int[nums.length];
int[] suffix_sum = new int[nums.length];
prefix_sum[0] = 1;
for (int i = 1; i < nums.length; i++) {
prefix_sum[i] = prefix_sum[i  1] * nums[i  1];
}
suffix_sum[nums.length  1] = 1;
for (int i = nums.length  2; i >= 0; i) {
suffix_sum[i] = suffix_sum[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
result[i] = prefix_sum[i] * suffix_sum[i];
}
return result;
}
Complexity analysis

Time complexity: The time complexity of the given code is
O(n)
, wheren
is the length of the input array nums. This is because: Calculating the
prefix_sum
products takeO(n)
time.  Calculating the
suffix_sum
products takeO(n)
time.  Constructing the
result
array takesO(n)
time.
 Calculating the
Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n)
= 3O(n)
, which is O(n)
.

Space complexity: The space complexity of the given code is
O(n)
. This is because: The
prefix_sum
array requiresO(n)
space.  The
suffix_sum
array requiresO(n)
space.  The
result
array requiresO(n)
space.
 The
All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n)
= 3O(n)
, which is O(n)
.
Approach 5: Carry Forward technique
Intuition
The carry forward technique optimizes us to solve the problem with a more efficient space complexity. Instead of using two separate arrays for prefix and suffix products, we can use the result array itself to store intermediate results and use a single pass for each direction.
Here’s how you can implement the solution using the carryforward technique:
Algorithm Steps for Carry Forward Technique
 Initialize Result Array:
 Create an array
result
of the same length asnums
to store the final results.
 Create an array
 Calculate Prefix Products:
 Initialize a variable
prefixProduct
to1
.  Iterate through the input array
nums
from left to right. For each indexi
, setresult[i]
to the value ofprefixProduct
. UpdateprefixProduct
by multiplying it withnums[i]
.
 Initialize a variable
 Calculate Suffix Products and Final Result:
 Initialize a variable
suffixProduct
to1
.  Iterate through the input array
nums
from right to left. For each indexi
, updateresult[i]
by multiplying it withsuffixProduct
. UpdatesuffixProduct
by multiplying it withnums[i]
.
 Initialize a variable
 Return the
result
array containing the product of all elements except the current element for each index.
Pseudocode
prefix products
prefixProduct = 1
For i from 0 to N1:
result[i] = prefixProduct
prefixProduct = prefixProduct * nums[i]
// Calculate suffix products and finalize result
suffixProduct = 1
For i from N1 to 0:
result[i] = result[i] * suffixProduct
suffixProduct = suffixProduct * nums[i]
Return result
Code
// carry forward technique
private static int[] carryForward(int[] nums) {
int n = nums.length;
int[] result = new int[n];
// Calculate prefix products
int prefixProduct = 1;
for (int i = 0; i < n; i++) {
result[i] = prefixProduct;
prefixProduct *= nums[i];
}
// Calculate suffix products and finalize the result
int suffixProduct = 1;
for (int i = n  1; i >= 0; i) {
result[i] *= suffixProduct;
suffixProduct *= nums[i];
}
return result;
}
Explanation
 Prefix Products Calculation:
 We initialize
prefixProduct
to1
and update each element ofresult
with the current value ofprefixProduct
.  Update
prefixProduct
by multiplying it withnums[i]
.
 We initialize
 Suffix Products Calculation:
 We initialize
suffixProduct
to1
and update each element ofresult
(which already contains the prefix product) by multiplying it withsuffixProduct
.  Update
suffixProduct
by multiplying it withnums[i]
.
 We initialize
Complexity analysis

Time Complexity:
O(n)
time 
Space Complexity:
O(n)
(for the result array)
This approach uses only a single extra array (result
) and two variables (prefixProduct
and suffixProduct
), achieving efficient space utilization while maintaining O(n)
time complexity.
Top comments (2)
Great resource! Foundational problems are solved using techniques that are used in many other problems. Once you learn these techniques, then you can solve a lot of other interview problems on your own.
None of the online tutorials or websites teach prefixsuffix sums. Thank you sir for writing the article.