1.
Introduction
2.
Naive Approach
3.
Optimized Approach
3.1.
PseudoCode
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Product of array except self

Urwashi Priya

## Introduction

In this blog, we will discuss an array problem that has been asked frequently in Interviews.

The problem is to find the Product of Array Except Self.

We are given an integer array, say nums, and we need to return another integer array, say the answer, such that answer[i] is equal to the product of all elements in nums except nums[i].

Example: Say, nums array = [1,2,3,4]

Output would answer array =  [24,2,8,6]

Another example:

Nums array= [-1,1,0,-3,3]

Also see, Euclid GCD Algorithm

## Naive Approach

The naive approach in finding the Product of Array Except Self is:

We will take a variable, say product, containing the product of all elements present in the array. Say, for example given array is [1,2,3,4].

∴product=24

To find the answer array, we need to divide 24 by the element present at that particular position.

But if we have to find the Product of Array Except Self without using division operation, then we will proceed as follows:

At any ith position, find the product of all elements on the left-hand side and the product of all elements on the right-hand side and then take their product.

Say, for example given array is [1,2,3,4].

Create a new array, say left, which will contain the product of all elements present on the left-hand side. So, for the given example left array would be [1,2,6,24].

Create a new array, say right, which will contain the product of all elements present on the right-hand side. So, for the given example right array would be [24,24,12,4]

For the 0th position, the output would be right[1]. This is because the answer of the first element in the array would be the product of all elements towards the right-hand side of that element.

For the last position, the output would be left[n-2]. This is because the answer of the last element in the array would be the product of all elements towards the left-hand side of that element.

For all other remaining position output would be left[i-1]*right[i+1]. This can be derived intuitively.

This approach takes O(n²) time, as two times array is traversed and space complexity becomes O(n).

So, we opt for an optimized approach.

## 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.

1. Any specific name for the approach used in the problem?
Answers)Yes, the two-pointer approach is used.
2. 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.

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

Live masterclass