*Correct me if i am wrong :)
*
**
Problem
**
We are given an array with integer elements , We need to result an array wher ith element is product of all the elements of orignal array but not self hence problem is Product of array expect self
**
First Thoughts
**Take two nested for loops , for each element iterate the whole array using inner loop make a product. Time Complexity - O(n^2)
Use a for loop to get a product of all the elements of the array..then divide product with each element which will give you the product expect self for each element.
Both of them are correct approach but given the problem constraints it is specified that You must write an algorithm that runs in O(n) time and without using the division operation.Where as the first approach gives time complexity of O(n^2) and second approach uses division operator(/) both of them are not allowed.
**
Correct Approach
**The correct approach here is to use the Prefix Product and Suffix Product.
What is prefix product?
**The word **Prefix mean before i.e Those who come before.
example - ABCD is given String or a word, so the prefix values of D are ABC.
In our case prefix product for each element will be product of that element and all the elements that has appeared before that element.
product of that element and all the elements that has appeared before that element
What is suffix product?
**The word **Suffix means after i.e Those who come after.
example - ABCD is given String or a word, so the suffix values of A are BCD.
In our case suffix product for each element will be product of that element and all the elements that has appeared after that element.
Key Insight
For ans element at i nums[i] = prefix[i-1] * suffix[i+1]
Edge case
Since At position 0 and last(nums.length - 1) their will be no before or after product so ,
prefix[0] = nums[0]
suffix[nums.length-1] = nums[nums.length - 1]
therfore answer for,
nums[i] = suffix[i+1] {if i == 0}
nums[nums.length - 1] = prefix[nums.length - 2] {if i == nums.length}
Top comments (0)