Published in

Nerd For Tech

# Product of Array Except Self

(Leetcode)

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in `O(n)` time and without using the division operation.

Example 1:

`Input: nums = [1,2,3,4]Output: [24,12,8,6]`

Example 2:

`Input: nums = [-1,1,0,-3,3]Output: [0,0,9,0,0]`

# Approach

1. Using the division operator

Time Complexity = O(n*n) where n is the size of the given array/ vector

Space Complexity = O(n) where you will store the values in a vector

`LOGIC : Multiply the other elements except nums[i], for eg : arr = [1,2,3] so for ans[0] = 2*3 = 6ans[1] = 1*3 = 3 ans[2] = 1*2 = 2 that is multiply the other elements except that element , so use the concept of using two loops. PS : Try to write on your own :) `

2. Without using the division operator

Time Complexity = O(n) where n is the size of the given array or vector

Space Complexity = O(n)

`LOGIC INVOLVED :1. I am using two vectors - one to store the left product and the other to store the right product. For eg :Taking the example [1,2,3]Left Product is the product of all elements to the left of the given number , leftProduct[0]= 1 (initialise all elements with 1)leftProduct[1]=leftProduct[0]*nums[0] = 1*1 = 1leftProduct[2]=leftProduct[1]*nums[1] = 1*2 = 2Similarly , rightProd[2] = 1 (initialise all elements with 1)rightProduct[1]=rightProduct[2]*nums[2] = 1*3 = 3rightProduct[0]=rightProduct[1]*nums[1] = 3*2 = 6nums[0] = leftProduct[0]*rightProd[0] = 1*6 = 6nums[1] = leftProduct[1]*rightProd[1] = 1*3 = 3nums[2] = leftProduct[2]*rightProd[2] = 2*1 = 2CODE :class Solution {public:    vector<int> productExceptSelf(vector<int>& nums) {                vector<int>leftProd(nums.size(),1);        vector<int>rightProd(nums.size(),1);                for(int i=1;i<nums.size();i++)            leftProd[i]=leftProd[i-1]*nums[i-1];                for(int i=nums.size()-1;i>=1;i--)            rightProd[i-1] = rightProd[i]*nums[i];                for(int i=0;i<nums.size();i++)            nums[i] = leftProd[i]*rightProd[i];                return nums;    }};`

Hope this helps! Keep coding!

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati

--

--

## More from Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

## Sukanya Bharati

A happy , motivated & a curious soul if you end up finding me 😎😁.