Difficulty: Medium, Asked-in: Facebook, Amazon, Morgan Stanley
Key takeaway: An excellent problem to learn problem-solving by storing the prefix and 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, 75, 0, 0, 0]
Example 4
Input: X[] = [1, 1, 1, 1, 1, 1, 1], Output: product[] = [1, 1, 1, 1, 1, 1, 1]
Solution idea
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:
Solution pseudocode
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
}
Solution analysis
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).
Solution idea
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!
Suppose we know two details for each element X[i]:
So the idea is: if we multiply the prefix product with the suffix product, we will get the product of elements excluding the current index i. In other words, product[i] = (product of all elements with an index less than i) * (the product of all elements with an index greater than i).
So, for implementing the above idea, we need to create two extra spaces prefixProduct[n] and suffixProduct[n] for storing prefix and suffix products for each index i. Here are some important formulas:
Solution pseudocode
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]
int 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
}
Solution analysis
Solution idea
Now 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:
Note: by traversing from the right end, we calculate suffixProduct and store the final output in product[] array using a single loop.
Solution steps
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 a variable suffixProduct with 1 and run a 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]
}
Solution pseudocode
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
}
Solution analysis
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!
Given an array, find the next greater element for every element in the array. The next greater element for an element is the first greater element on the right side of the array. This is one of the best problems to learn problem-solving using stack.
Given a string S[], write a program to sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. If two characters have the same frequency, whichever occurs earliest in S, must come first. In other words, the sorting must be stable.
Write a program to find the equilibrium index of an array. An array's equilibrium index is an index such that the sum of elements at lower indexes equals the sum of elements at higher indexes. This is an excellent coding question to learn time and space complexity optimization using several approaches.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.