Product of array except self

Difficulty: Medium, Asked-in: Facebook, Amazon, Morgan Stanley

Key takeaway: This problem is an excellent opportunity to learn step-by-step optimization using prefix arrays and a single loop with 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 entire array) fits into 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 at least 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 * 3 = 6

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]

Discussed solution approaches

• Brute force solution using nested loops
• Using extra space and loop : prefix and suffix product array
• Efficient in-place solution using a single loop 

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: the outer loop from i = 0 to n - 1 to pick each element X[i] and the inner loop from j = 0 to n - 1 to calculate the product excluding X[i]. Before starting the inner loop, we also initialize the 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 output by the end of the nested loop.

Solution code C++

vector<int> productExceptSelf(int X[], int n) 
{
    vector<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;
}

Python implementation

def productExceptSelf(X, n):
    product = [0] * n
    for i in range(n):
        prodExclCurr = 1
        for j in range(n):
            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).

Using prefix and suffix product array

Solution idea

We are running two nested loops and performing constant or O(1) operations at each iteration. So, the time complexity is O(n^2) * O(1) = O(n^2). Since we are using constant extra space, the space complexity is O(1).

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!

If we observe the output pattern, the product of all elements except X[i] is equal to the product of all elements from X[0] to X[i - 1] multiplied by the product of all elements from 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 the 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].

• prefixProduct[i - 1] = the product of elements from index 0 to i - 2.
• prefixProduct[i] = the product of elements from index 0 to i - 1.
• prefixProduct[i] = prefixProduct[i - 1] * X[i - 1]

For i = 0, there is no element on the left of the array. So we initialize prefixProduct[0] with 1, and the 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].

• suffixProduct[i+1] = product of elements from index i+2 to n-1.
• suffixProduct[i] = product of elements from index i+1 to n-1.
• suffixProduct[i] = suffixProduct[i+1] * X[i+1]

For i = n-1, there is no element to the right of the array. So we initialize suffixProduct[n-1] with 1 and the 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]

Solution code C++

vector<int> productExceptSelf(int X[], int n) 
{
    vector<int> prefixProduct(n);
    vector<int> suffixProduct(n);
    vector<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;
}

Python implementation

def productExceptSelf(X, n):
    prefixProduct = [0] * n
    suffixProduct = [0] * n
    product = [0] * n
    
    prefixProduct[0] = 1
    for i in range(1, n):
        prefixProduct[i] = X[i-1] * prefixProduct[i-1]
        
    suffixProduct[n-1] = 1         
    for i in range(n-2, -1, -1):
        suffixProduct[i] = X[i+1] * suffixProduct[i+1]
        
    for i in range(n):
        product[i] = prefixProduct[i] * suffixProduct[i]
    
    return product

Solution analysis

We are using three single loops, where each loop runs 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).

An efficient in-place solution using a single loop

Solution Idea

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!

To find the product of all elements except X[i], we need two pieces of information: the prefix product from i=0 to i-1 and the suffix product from i=n-1 to i+1. So we can make two modifications to the previous solution:

1. In the beginning, we can use the 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. The critical question is: How do we find the suffix product for each element without using extra memory? For this, we traverse the array from index n-1 to 0, and at each iteration:
3. We calculate the running suffix product and store this value in a variable called suffixProduct.
4. We multiply the suffixProduct with the prefix product stored at the product[i] and store this value at the product[i].

Note: By traversing from the right end, we can do two things together: calculating suffixProduct and storing the final output in the product[].

Solution Steps

• We declare the product[n] array and initialize 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 the variable suffixProduct with 1 and run a loop from i=n-1 to 0. At each iteration, we do two things: 1) We store the value at product[i] by multiplying product[i] with suffixProduct. 2) We calculate the 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 code C++

vector<int> productExceptSelf(int X[], int n) 
{
    vector<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] *= suffixProduct;
        suffixProduct *= X[i];
    }

    return product;
}

Python implementation

def productExceptSelf(X, n):
    product = [0] * n
    product[0] = 1
    for i in range(1, n):
        product[i] = X[i-1] * product[i-1] 
        
    suffixProduct = 1
    for i in range(n-1, -1, -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.

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 array: Time = O(n), Space = O(n)
• Using the output array itself: Time = O(n), Space = O(1)

Suggested coding problems to explore

• Equilibrium index solution using prefix array 
• Trapping rainwater solution using prefix array
• Maximum difference between two elements
• [Find maximum j - i such that X[j] > X[i]](https://www.enjoyalgorithms.com/blog/find-the-maximum-j-i-in-array/)
• Find the sum of all subarrays

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!