Optimized Approach
To minimize the time complexity, we can find the Product of Array Except Self using this method.
The time complexity for this problem will reduce from O (n²) to O (n).
The only change we will be making here would be instead of maintaining the product towards the right-hand side in the right array, we will track in a variable named product and keep it updating.
Create a new array, say output, which will contain the product of all elements present on the left-hand side. So, for the given example output array would be [1,2,6,24].
⬇
The product of all elements present on the right-hand side will be tracked by a variable(say product). So, it will be first initialised to 1. Then it would become 4, then 12, then 24, and so on.
⬇
The ultimate goal is to find a product of all elements towards the left and the product of all elements towards the right. ( i.e. output[i]=output[i-1]*product)
⬇
At the first position, we would get the product of all elements present towards the right-hand side, already stored in a variable(i.e.product).
⬇
Return Output.
Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.
https://www.codingninjas.com/studio/problems/product-of-array-except-self_630271
If you were not able to solve it, don’t be sad.
Please have a look at the algorithm, and then again, you must give it a try.
PseudoCode
Algorithm
___________________________________________________________________
procedure productOfArrayExceptSelf(nums ):
___________________________________________________________________
1. Find the size of nums array. int n=nums.size()
2. Declare a vector, say output, which will keep track of the product of elements towards the left-hand side. vector<int> output
3. If no element is present in the array, just return the output array.
4. Now, for the output array, start for loop from 0 to n.
5. product =product* nums[i];
output.push_back(product)
6. To keep track of the product of elements towards the right-hand side, we declare a variable, say product.
7. To find output, start for loop from n-1 till 0.
8. output[i]=output[i-1]*product; product*=nums[i];
9. At the first position, we would get the product of all elements present towards the right-hand side, which is already stored in a variable(i.e.product).
10. Return output.
end procedure
___________________________________________________________________
Implementation in C++
Now, let’s have a look at the Code:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int nums[n];
for(int i=0; i<n; i++){
cin>>nums[i];
}
//finding the size of nums array
vector<int> output;
//if no element is present in the array, just return the output array.
if(n<1){
for(int i=0; i<n; i++){
cout<<output[i]<<" ";
}
}
int product=1;
//Storing product of all elements present on the left-hand side of element at the ith position in the output array.
for(int i=0; i<n; i++){
product *= nums[i];
output.push_back(product);
}
//product of all elements present on the right-hand side of element at the ith position will be tracked by a variable(say product).
product=1;
for(int i=n-1; i>0; i--){
//Ultimate goal is to find the product of all elements towards the left and the product of all elements right-hand towards the right.
output[i]=output[i-1]*product;
product*=nums[i];
}
//At the first position, we would get the product of all elements present towards the right-hand side, which is already stored in a variable(i.e.product).
output[0]=product;
for(int i=0; i<n; i++){
cout<<output[i]<<" ";
}
}
Output
Sample Input:
4
1 2 3 4
Sample Output:
24 12 8 6
Complexity Analysis
Time Complexity: O(n).
Analyzing Time Complexity:
Since we have to do for n iterations, i.e. traverse only once.
Space complexity: O(1) since only a product variable is used.
Frequently Asked Questions
-
Any specific name for the approach used in the problem?
Answers)Yes, the two-pointer approach is used.
-
When to use two pointer approach?
Answers)When one pattern starting from the beginning runs at a slow pace whereas one starting from the end runs fast. It saves a lot of time.
Key Takeaways
This article taught us how to find the product of an array except self by approaching the problem using a two-pointer approach. We discussed its implementation using illustrations, pseudocode, and then proper code.
Read more about: Array in Javascript
We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the pattern followed in most array problems.
Now, we recommend you practice problem sets based on arrays to master your fundamentals. You can get a wide range of questions similar to this on Coding Ninjas Studio.
305+ registered