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 righthand 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 lefthand side. So, for the given example output array would be [1,2,6,24].
⬇
The product of all elements present on the righthand 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[i1]*product)
⬇
At the first position, we would get the product of all elements present towards the righthand 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/productofarrayexceptself_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 lefthand 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 righthand side, we declare a variable, say product.
7. To find output, start for loop from n1 till 0.
8. output[i]=output[i1]*product; product*=nums[i];
9. At the first position, we would get the product of all elements present towards the righthand 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 lefthand 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 righthand side of element at the ith position will be tracked by a variable(say product).
product=1;
for(int i=n1; i>0; i){
//Ultimate goal is to find the product of all elements towards the left and the product of all elements righthand towards the right.
output[i]=output[i1]*product;
product*=nums[i];
}
//At the first position, we would get the product of all elements present towards the righthand 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 twopointer 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 twopointer 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.