Problem:
Given an array of integers , find an array of products where each product is the product of all the numbers except the element in that index.
ie) For every number number[i] , find the product of all the numbers except number[i]
Input:
numbers = [1,2,3,4]
Output:
[24,12,8,6]
Calculated as below:
24 = 2*3*4
12 = 1*3*4
8 = 1*2*4
6 = 1*2*3
eg) product[0] = number[1]* number[2]*number[3]
product[1] = number[0]*number[2]*number[3]
Try out the solution here:
https://leetcode.com/problems/product-of-array-except-self/
Solution:
The brute force solution to the above problem is to take each element and iterate through all the elements except the original element and multiply them.
This requires two nested for loops and the time complexity is O(n2 ) as shown below:
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] product = new int[nums.length];
//initialize all the sum to 1
for(int i=0; i < nums.length;i++){
product[i]=1;
}
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums.length ;j++){
if(j!=i){
product[i]= product[i]*nums[j];
}
}
}
return product;
}
}
Better solution:
A better solution of time complexity O(n) is this:
Hint:
- Traverse the array twice once from the beginning and then from the end
- Find the product of all the numbers to the left of each element during the left traversal
- Find the product of all the numbers to the right of each element during the right traversal
- Multiple both the above products
ALGORITHM:
Here is an algorithm which uses the above hints. The algorithm also uses extra storage to store the left product and the right product (O(n) + O(n) = O(2n) which can be considered as O(n)). Even better is to use only one extra storage which will be discussed next to this algorithm.
STEP1: Initialize three arrays – one to store the product of all the numbers to the left of each element , another to store the product of all the numbers to the right of each element and another to store the final product
STEP2: For the first element , there are no elements to the left , so initialize the “left product” of the first element to 1
STEP3: For the last element , there are no elements to the right, so initialize the “right product” of the last element to 1.
STEP4: For each element in the array starting from the beginning and ignoring the first element, calculate the product of the previous element and the product of all the numbers to the left of the previous element (“left product”) and store them in the corresponding index of the “left product” array.
STEP5: For each element in the array starting from the end ignoring the last element, calculate the product of the next element and the product of all the numbers to the right of the next element (“right product”) and store them in the corresponding index of the “right product” array.
STEP6: For each element in the array , multiply the “left product” obtained in step 4 with the “right product” obtained in step 5
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] leftProduct = new int[nums.length];
int[] rightProduct = new int[nums.length];
int[] finalProduct = new int[nums.length];
leftProduct[0]=1;
rightProduct[nums.length-1]=1;
for(int i=1;i<nums.length;i++){
leftProduct[i]= leftProduct[i-1]*nums[i-1];
}
for(int i=nums.length-2;i >= 0;i--){
rightProduct[i]= rightProduct[i+1]*nums[i+1];
}
for(int i=0;i<nums.length;i++){
finalProduct[i] = leftProduct[i] * rightProduct[i];
}
return finalProduct;
}
}
Let’s see how this works by examining a sample.
Consider the input:
input = [1,2,3,4]
You assign the first element to leftProduct[0]:
leftProduct[0] = 1
and assign the last element to rightProduct[3]
rightProduct[3] = 4
First iteration in first for loop:
Since you ignore the first element , the element traversed is the element in the second index position , input[1] which is 2
The element to the left of this element is input[0] is 1.
The left product of the element 1 is 1 (since there are no elements to its left and the left product is initialized to 1)
So the value is left element * left product of the element which is 1* 1 = 1
so leftProduct[1] = 1
leftProduct array values are now – [1,1]
Second iteration in first for loop:
The element traversed is the element in the third index , input[2] which is 3.
The element to the left of this element is input[1] which is 2
The left product of the element 2 (calculated in the previous iteration) is 1.
So the value is left element * left product which is 2*1 = 2.
leftProduct array values are now – [1,1,2]
Third iteration in the first for loop:
The last element traversed is the element in the fourth index , input[3] which is 4.
The element to the left of this element in input[2] which is 3.
The left product of the element 3 (calculated in the previous iteration) is 2.
So the value is left element * left product which is 3 * 2 = 6
So the final leftProduct array values are [1,1,2,6]
Similarly starting from the right you calculate the rightProduct array which is [24,12,4,1].
Now you multiply each element in the leftProduct array with corresponding element in the rightProduct array and you get the final output [24,12,8,6].
The above algorithm has three for loops so the time complexity is O(3n) which can be considered as O(n)
It requires two extra arrays apart from the output array so the total space complexity is O(3n) which can be considered as O(n).
This can be further improved by removing the extra two arrays and use a “temporary variable” instead as shown in the next solution:
Optimal solution:
The optimal solution requires the same O(n) time complexity but the extra space complexity is just O(1) (temporary variable) instead of O(2n) (left product array and right product array).
Hint:
Instead of left product array and right product arrays , just use a temporary variable.
Explanation in detail:
- You consider the left product array used in the previous algorithm to be a temporary variable . Initially this is set to 1 since the first element has no previous elements, you assign this to the first element of the final product array.
- For each element in the array starting from the beginning, you multiply this temporary variable with the value of the current element so that it represents the left product for the next element . This will be assigned to the next element in the product array. Keep doing this for each element in the array
- Similarly you consider the right product array to be a temporary variable (you can reuse the same temporary variable used before). You start from the end this time. Initially the temporary value is set to 1 since there are no elements to the right of the last element. This value (right product) is multiplied with the value obtained in the previous step for the same index position( left product) to get the final value in the final product array.
- Also you multiply the temporary variable with the value of the current element so that it represents the right product for the next element, keep doing this until you reach the beginning of the array.
ALGORITHM:
STEP1: Declare an array to store the final output
STEP2: Initialize a temporary variable to the value 1 . This represents the product of all the elements to the left of an element as we traverse the array from the beginning. Similarly it represents the product of all the elements to the right of an element as we traverse the array from the end
STEP3: For each element in the array from the beginning , assign the temporary variable to the product array
STEP3 a: Also multiple the temporary variable to the element in the current index and assign it to itself. This represents the “left product” for the next element.
STEP4: Reset the temporary variable to the value 1 again.
STEP5: For each element in the array from the end, multiply the temporary variable with the value in the output product array computed in step 3 and assign it to the product array. This represents the final value in the index position.
STEP5a : Also multiple the temporary variable to the element in the current index and assign it to itself. This represents the “right product” for the next element
class Solution {
public int[] productExceptSelf(int[] nums) {
int product[] = new int[nums.length];
int temp = 1;
for(int i=0;i<nums.length;i++){
product[i] = temp ;
temp = temp * nums[i];
}
temp = 1;
for(int i=nums.length-1;i >=0 ;i--){
product[i] = temp * product[i];
temp = temp * nums[i];
}
return product;
}
}
The above solution requires two separate for loops , so time compexiy is O(2n) which can be considered as O(n).
Also apart from the final “product” output array we use just one extra storage – the “temp” variable. So the extra space complexity required is O(1) ( Total space complexity is still O(n) – product array O(n) + temporary variable O(1) which is negligible)
This is an existing standard solution discussed in the popular portals leetcode and geeksforgeeks. But most of them initialize the final product array to the value of 1 for all the elements which is not required . I removed this and submitted the solution to leetcode and was surprised to see this:
The solution we just discussed just took 1 ms on leetcode servers and was the fastest as of the time of submission!
Woohoo!
Leave a Reply