Nerd For Tech
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 = 6
ans[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 = 1
leftProduct[2]=leftProduct[1]*nums[1] = 1*2 = 2
Similarly , rightProd[2] = 1 (initialise all elements with 1)
rightProduct[1]=rightProduct[2]*nums[2] = 1*3 = 3
rightProduct[0]=rightProduct[1]*nums[1] = 3*2 = 6
nums[0] = leftProduct[0]*rightProd[0] = 1*6 = 6
nums[1] = leftProduct[1]*rightProd[1] = 1*3 = 3
nums[2] = leftProduct[2]*rightProd[2] = 2*1 = 2
CODE :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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store