Difficulty: Medium, Asked-in: Facebook, Amazon, Morgan Stanley
Key takeaway: An excellent problem to learn step-by-step optimization using prefix array and a single loop using variables.
Given an array X[] of n integers where n > 1, write a program to return an array product[] such that product[i] is equal to the product of all the elements of X except X[i].
Important note: Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
Example 1
Input: X[] = [2, 1, 3, 4], Output: product[] = [12, 24, 8, 6]
Explanation:
Example 2
Input: X[] = [5, 2, 8, 4, 5], Output: product[] = [320, 800, 200, 400, 320]
Example 3
Input: X[] = [1, 0, 4, 3, 5], Output: product[] = [0, 60, 0, 0, 0]
Example 4
Input: X[] = [1, 1, 1, 1, 1, 1, 1], Output: product[] = [1, 1, 1, 1, 1, 1, 1]
Example 5
Input: X[] = [0, 4, 0, 3], Output: product[] = [0, 0, 0, 0]
The basic idea would be to traverse the array, find the product of each element except the current element and store it in the output array. To implement this:
int[] productExceptSelf(int X[], int n)
{
int product[n]
for (int i = 0; i < n; i = i + 1)
{
int prodExclCurr = 1
for (int j = 0; j < n; j = j + 1)
{
if (i == j)
continue
prodExclCurr = prodExclCurr * X[j]
}
product[i] = prodExclCurr
}
return product
}
We are running two nested loops and performing constant or O(1) operations at each iteration. So time complexity = O(n^2) * O(1) = O(n^2). We are using constant extra space, so space complexity = O(1).
Now the critical question is: can we solve this problem using a single loop in O(n) time complexity? Can we use extra space and store some intermediate values to get an O(n) solution? Let's think!
If we observe the output pattern, Product of all elements except X[i] = (Product of all elements from X[0] to X[i - 1]) * (Product of all elements X[i + 1] to X[n - 1]). So if we multiply the prefix product with the suffix product, we will get the product of elements excluding the current index.
To implement this idea, we need to create two extra arrays, prefixProduct[n] and suffixProduct[n], to store prefix and suffix products for each index i. How do we store values in both arrays? Let's think!
Calculation of prefixProduct[n]: We can store the prefix array by calculating the running product using a single loop starting from the left. The idea is simple: If we know the value of prefixProduct[i - 1], we can easily calculate prefixProduct[i].
For i = 0, there is no element on the left of array. So we initialise prefixProduct[0] with 1 and loop will run from i = 1 to n - 1.
prefixProduct[0] = 1
for (int i = 1; i < n; i = i + 1)
prefixProduct[i] = X[i - 1] * prefixProduct[i - 1]
Calculation of suffixProduct[n]: Similarly, we can store the suffix product array by calculating the running product using a single loop starting from the right end. The idea is simple: If we know the value of suffixProduct[i + 1], we can easily calculate suffixProduct[i].
For i = n - 1, there is no element on the right of the array. So we initialise suffixProduct[n - 1] with 1 and loop will run from i = n - 2 to 0.
suffixProduct[n - 1] = 1
for (int i = n - 2; i >= 0; i = i - 1)
suffixProduct[i] = X[i + 1] * suffixProduct[i + 1]
Finally, we run another single loop to store the product excluding each element in the output array. product[i] = prefixProduct[i] * suffixProduct[i]
for (int i = 0; i < n; i = i + 1)
product[i] = prefixProduct[i] * suffixProduct[i]
int[] productExceptSelf(int X[], int n)
{
int prefixProduct[n]
int suffixProduct[n]
int product[n]
prefixProduct[0] = 1
for (int i = 1; i < n; i = i + 1)
prefixProduct[i] = X[i - 1] * prefixProduct[i - 1]
suffixProduct[n - 1] = 1
for (int i = n - 2; i >= 0; i = i - 1)
suffixProduct[i] = X[i + 1] * suffixProduct[i + 1]
for (int i = 0; i < n; i = i + 1)
product[i] = prefixProduct[i] * suffixProduct[i]
return product
}
We are using three single loops, where each loop is running n times. Time complexity = Time complexity to store prefixProduct[] + Time complexity to store suffixProduct[] + Time complexity to store values in product[] = O(n) + O(n) + O(n) = O(n).
We are using two extra arrays of size n. So space complexity = O(n) + O(n) = O(n)
The critical question is: Can we optimize the above method to work in O(1) space complexity? Do we need to store both prefix and suffix product arrays? Think!
For finding the product of all element except X[i], we need two informations: Prefix product from i = 0 to i - 1 and suffix product from i = n - 1 to i + 1. So we can do two modifications to the previous solution:
Then we multiply each element product[i] with its suffix product and store it at the same index i in the product[] array. The critical question is: How do we find suffix product for each element without using extra memory? For this, we traverse array from index n - 1 to 0 and at each iteration:
Note: By traversing from the right end, we can do two things together: Calculating suffixProduct and storing the final output in the product[].
Now we run a loop to store the prefix product in product[].
for (int i = 1; i < n; i = i + 1)
product[i] = X[i - 1] * product[i - 1]
We initialize variable suffixProduct with 1 and run loop from i = n - 1 to 0. At each iteration, we do two things: 1) We store value at the product[i] by multiplying product[i] with suffixProduct 2) We calculate suffixProduct for the next iteration by multiplying suffixProduct with X[i].
int suffixProduct = 1
for (int i = n - 1; i >= 0; i = i - 1)
{
product[i] = product[i] * suffixProduct
suffixProduct = suffixProduct * X[i]
}
int[] productExceptSelf(int X[], int n)
{
int product[n]
product[0] = 1
for (int i = 1; i < n; i = i + 1)
product[i] = X[i - 1] * product[i - 1]
int suffixProduct = 1
for (int i = n - 1; i >= 0; i = i - 1)
{
product[i] = product[i] * suffixProduct
suffixProduct = suffixProduct * X[i]
}
return product
}
Important note: We recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!
Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.