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.

Let’s understand the problem!

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].

• It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32-bit integer.
• We need to solve this problem without using division operations.

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:

• Product except the 1st element = 1 * 3 * 4 = 12
• Product except the 2nd element = 2 * 3 * 4 = 24
• Product except the 3rd element = 2 * 1 * 4 = 8
• Product except the 4th element = 2 * 1 * 4 = 8

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]

Discussed solution spproaches

• A brute force solution using nested loops
• Using extra space and loop : prefix and suffix product array
• An efficient in-place solution using a single loop 

Solution approach 1: A brute force solution using nested loops

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:

• We take an output array product[] of size n.
• Now we use two nested loops: an outer loop from i = 0 to n - 1 to pick each element X[i] and an inner loop from j = 0 to n - 1 to calculate the product excluding X[i]. Before starting the inner loop, we also initialize a variable prodExclCurr to store the desired product.
• Inside the inner loop, when i == j, we ignore the current element and move to the next iteration. Otherwise, we update the variable prodExclCurr i.e. prodExclCurr = prodExclCurr * X[j]. So, by the end of the inner loop, we store the calculated product excluding X[i] at the product[i].
• Similarly, at each iteration of the outer loop, we incrementally calculate and store values in the product[] array. So, we return the product[] array as an output by the end of the nested loop.

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 approach 2: Using prefix and suffix product array

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]:

• Prefix product: The product of each element from index 0 to i - 1.
• Suffix product: The product of each element from index i + 1 to n - 1.

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:

• prefixProduct[i] = X[i] * prefixProduct[i - 1]
• suffixProduct[i] = X[i] * suffixProduct[i - 1]
• product[i] = prefixProduct[i] * suffixProduct[i]

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

• 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)

Solution approach 3: An efficient in-place solution using a single loop 

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:

1. In the start, we can use product[] array itself to store the prefix product i.e. product[i] = X[i - 1] * product[i - 1].
2. Then we multiply each element product[i] with its suffix product and store it at the same index i in the product[] array. But the critical question is: how do we find the value of the suffix product for each element without using extra memory? One idea would be: Traverse the array from right to left from index n - 1 to 0 and at each iteration:
3. We calculate the running suffix product and store it in a variable suffixProduct.
4. We multiply suffixProduct with prefix product stored at the product[i].
5. We store the multiplied result at the product[i].

Note: by traversing from the right end, we calculate suffixProduct and store the final output in product[] array using a single loop.

Solution steps

• We declare an product[n] array and intialize product[0] with 1.

• 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]
  }
  

• Finally, we return the value stored in the product[] array.

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

• We are using two single loops. So time complexity = O(n) + O(n) = O(n).
• We are using constant extra space. So space complexity = O(1). Here output array does not count as extra space for space complexity 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!

Critical ideas to think!

• Can we solve this problem using some other approaches?
• Using division operation, can we solve it using O(n) time and O(1) space?
• Can we try to solve this problem using recursion?
• In the 2nd approach, before starting the loop, why are we initializing prefixProduct[0] and suffixProduct[n - 1] with value 1?
• In the 2nd loop in the 3rd approach, why are we calculating the value of suffixProduct after storing value at output[i]?

Comparison of time and space complexities

• Using nested loops: Time = O(n^2), Space = O(n)
• Using prefix and suffix product array: Time = O(n), Space = O(n)
• Using the output array itself: Time = O(n), Space = O(1)

Suggested coding problems to explore

• Find equilibrium index of an array
• Move zeroes to the end of an array
• Valid Mountain Array
• The minimum and maximum value in an array
• The maximum difference between two elements

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!