238. Product of Array Except Self Leetcode Solution
Product of Array Except Self Leetcode Problem :
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.
Product of Array Except Self Leetcode Solution :
Constraints :
- 2 <= nums.length <= 105
- -30 <= nums[i] <= 30
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Example 1:
- Input: nums = [-1,1,0,-3,3]
- Output: [0,0,9,0,0]
Intuition :
The code aims to find an array ans where ans[i] is the product of all elements in the original array nums except nums[i]. To achieve this, the code computes two auxiliary arrays pre and suff. pre[i] represents the product of all elements in nums from index 0 to i-1, and suff[i] represents the product of all elements in nums from index i+1 to the end.
Approach :
Prefix and Suffix Products:
Create two arrays, pre and suff, to store products from the left and right sides of each element.
Compute Prefix Products:
Go through the array from left to right and fill the pre array. For each element, pre[i] will store the product of all elements to its left.
Compute Suffix Products:
Go through the array from right to left and fill the suff array. For each element, suff[i] will store the product of all elements to its right.
Calculate Final Products:
For each element in the original array:
Multiply the product of elements to its left (pre[i-1] if i >= 1).
Multiply the product of elements to its right (suff[i+1] if i <= n-1).
Store this product in the new array.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution
{
public:
vector< int> productExceptSelf(vector< int> &nums)
{
int n = nums.size();
vector< int> pre(n + 1, 1);
vector< int> suff(n + 1, 1);
vector< int>ans(n,0);
pre[0] = nums[0];
for (int i = 1; i < n; i++)
{
pre[i] = pre[i - 1] * nums[i];
}
suff[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 1; i--)
{
suff[i] = suff[i + 1] * nums[i];
}
for(int i=0;i< n;i++){
int a=1;
int b=1;
if(i>=1){
a=pre[i-1];
}
if(i< =n-1){
b=suff[i+1];
}
ans[i]=a*b;
}
for(int i=0;i< n;i++){
cout<< pre[i]<<" ";
}cout<< endl;
for(int i=n-1;i>=0;i--){
cout<< suff[i]<<" ";
}
cout<< endl;
return ans;
}
};
class Solution {
public int[] productExceptSelf(int[] nums) {
int ans[] = new int[nums.length];
int pre=1;
for(int i=0; i< nums.length; i++ ){
ans[i]=pre;
pre*=nums[i];
}
pre =1;
for(int i=nums.length-1; i>=0; i--){
ans[i]*=pre;
pre*=nums[i];
}
return ans;
}
}
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
length = len(nums)
products = [1] * length
for i in range(1, length):
products[i] = products[i-1] * nums[i-1]
right = nums[-1]
for i in range(length-2, -1, -1):
products[i] *= right
right *= nums[i]
return products
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment