Scribble 7: Product Array

Here’s the problem statement:

Given an array of integers, return a new array of the same length as the given array such that the result array’s value at index i = product of elements at all indices of the input array except the element at the i^th index.

For example:
The array: [1, 3, 5, 6, 1]
Output: [19, 30, 18, 15, 90]

Let’s dive into the solution:

It is interesting to note that this problem’s solution requires an approach similar to the one we used for the Trapping Rain Water problem. This is because in both the problems the answer value at the i^th index depends on the values that lie to the left of the i^th index and those that lie to the right of it in the input array.

Approach 1:

This is a naive approach: Here’s the steps:

Loop through all indices in the array using a for loop to build the ans array as:
At every index:
- move towards its left till the 0^th index and store the product of all these elements in a variable leftProd
- move towards its right till the last index and store the product of all these elements in a variable rightProd
- set ans[i] = leftProd*rightProd

Time complexity: O(N²) because at every index i (where i goes from 0 to n), we loop over all indices in the array. Therefore, totally, we loop over N² indices throughout the algorithm.

Space complexity: O(1) (other than the space needed to store the ans array)

Here’s the code for this solution in Java:

public int[] prodArray(int[] array) {
    int prodLeft, prodRight;
    prodLeft = prodRight = 1;
    int ans[] = new int[array.length];
    for(int i=0;i<array.length;i++) {
        prodLeft = prodRight = 1;
            for(int j = i-1;j>=0;j--) {
            prodLeft = prodLeft*array[j]; 
        }
        for(int j = i+1;j<array.length;j++) {
            prodRight = prodRight*array[j]; 
        }
			ans[i] = prodLeft*prodRight;
		}
 
    return ans;      
 
}

Approach 2:

This time we’re gonna do better than O(N²) by using some space. This similar to Approach 2 of the Trapping Rain Water problem.

Here are the steps:

Loop over the array from the left to right storing at every index the product of all elements to the left of it in another array leftProd[] as: leftProd[i] = leftProd[i-1]*array[i-1]
Next, loop over the array one more time from the right to the left keeping variable rightProd to store the product of all elements to to the right of every index and updating ans[i] = leftProd[i]*rightProd.

A side note on the style of programming: The last loop can be designed in two ways:

rightProd = 1;
for(int i = array.length-1;i>=0;i--) {
	ans[i] = leftProd[i]*rightProd;
	rightProd = rightProd*array[i];
}

Here, we run from the last element to the 0^th element in the array and at every element we technically update rightProd for the next element i.e. the (i-1)^th index. [rightProd for the last element is of course 1 and is set before the loop.]

Another way to design this loop is:

ans[ans.length-1] = leftProd[leftProd.length-1];
for(int i = array.length-2;i>=0;i--) {
	rightProd = rightProd*array[i+1];
	ans[i] = leftProd[i]*rightProd;
}

Here we run from the second last element to the 0th element and at every element we update rightProd for itself i.e. for the i^th index and then set ans[i]. [ans[i] for the last element is of course leftProd for the last index and is set before the loop.]

Though both ways are technically correct and accepted, I personally consider the first one slightly better because there we run through all the elements and do not have to be careful to start from the (array.length-2)^th index and we are also are saved from the highly likely incident of forgetfulness leading to the absence of the statement: ans[ans.length-1] = leftProd[leftProd.length-1]; in the final code.

Time complexity: O(N) because every element is visited only twice throughout the algorithm

Space complexity: O(N) because we use an extra array leftProd (other than the space needed to store the ans array, in fact, with it too the space complexity = O(N))

Here’s the code for this solution in Java:

public int[] prodArray(int[] array) {

    int leftProd[] = new int[array.length];
    int rightProd = 1;
    int ans[] = new int[array.length];
    Arrays.fill(leftProd, 1);
		
    for(int i = 1;i<array.length;i++) {
	leftProd[i] = leftProd[i-1]*array[i-1];
     }
     for(int i = array.length-1;i>=0;i--) {
	ans[i] = leftProd[i]*rightProd;
	rightProd = rightProd*array[i];
     }
     return ans;
  }

Approach 3:

Here’s a way of solving this problem in O(N) time and O(1) space:

Initialise 2 variables leftProd and rightProd to 1.
Initialise ans array with all elements set to 1
Loop through the array from left to right setting at every index ans[i] = ans[i]*leftProd and then updating leftProd for the next index setting it to be = leftProd*array[i].
Loop through the array from right to left setting at every index ans[i] = ans[i]*rightProd and then updating rightProd for the next index setting it = rightProd*array[i].

Time complexity: O(N) because every element is visited only twice throughout the algorithm

Space complexity: O(1) (other than the space needed to store the ans array)

Here’s the code for this solution in Java:

public int[] prodArray(int[] array) {
                int leftProd = 1;
		int rightProd = 1;
		int ans[] = new int[array.length];
		
		for(int i = 0;i<array.length;i++) {
			ans[i] = leftProd;
			leftProd = leftProd*array[i];
		}
 
		for(int i = array.length-1;i>=0;i--) {
			ans[i] *= rightProd;
			rightProd = rightProd*array[i];
		}
		return ans;
  }

Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂

Share this:

Related