LeetCode Challenge #238. Product of Array Except Self

Day 14 of 100 Days LeetCode Challenge

Question 7 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #238. Product of Array Except Self

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]

Constraints:

2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Java Video Solution

C++ Video Solution

Java Solution

				
					class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] right = new int[n];
        int pro = 1 ;

        for(int i=n-1;i>=0;i--){
            pro = pro * nums[i];
            right[i] = pro ;
        }
        int[] ans = new int[n];
        int left = 1 ;

        for(int i=0;i<n-1;i++){
            int val = left * right[i+1];
            ans[i] = val ;
            left = left * nums[i];
        }
         ans[n-1] = left ;
         return ans ;
    }
}

C++ Solution

				
					class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {

        int n=nums.size();
        vector<int> leftpr(n,1);
        vector<int> rightpr(n,1);

        for(int i=1;i<n; i++)
        {
            leftpr[i]=leftpr[i-1]*nums[i-1];
        }
        for(int i=n-2; i>=0; i--)
        {
            rightpr[i]=rightpr[i+1]*nums[i+1];
        }

        for(int i=0; i<n; i++)
        {
            nums[i]=leftpr[i]*rightpr[i];
        }

        return nums;
        
    }
};

Code Explanation

In this program we have to reverse the order of words,but keeping the word’s direction in the same way. Only the words will be interchanged .

In this question , We have to find the product of every element in an array except itself.

In simpler terms , we have to find a new list where each number is the result of multiplying all the numbers in the original list, except the one at the same position.

In this approach we have to maintain the time complexity of O(n) and space complexity’s O(n).

Let’s see the step-by-step approach of the code:

1.For this purpose we are using two additional arrays, ‘leftptr’ and ‘rightptr’ , to store the product of elements to the left and right of each element, respectively.

For obtaining the product of backward Elements from the current position ,we will multiply In this manner :

left of (i -1) th positions will be the product of (i-2th) so if we

Multiply left[ i -1] * nums [ i -1 ]

Then we can get the product upto (i-1)th position.

In this way we are able to find out the product of all the backward elements from the current position in an array.

For Right side also same iteration would be followed like :

Right[i+1] * num[ i+1]

Now Easily, we have obtained both the products of left and right side and if we multiply left and right products together we will get the Total Product .

Initialise an integer ‘n’ starting from 1 to calculate the size of input vector ‘nums’ .

Vector<int> leftpr( n, 1);

Vector<int> rightpr( n, 1);

let’s start the ‘for’ loop which calculates the product of all elements to the left of each element and stores the result in ‘leftpr’. Also, it starts from index 1 and update each element by multiplying it with previous element in ‘nums’ .

Similarly, the second ‘for’ loop is for calculating the product of all elements to the right of each element and stores the result in ‘rightpr’ . Here, it starts from second last element and updates each element as it move forward.

The Third ‘for’ loop is for calculating the final result by multiplying the elements of ‘leftpr’ and ‘rightpr together .

Finally, the modified ‘nums’ vector containing the product of all elements except for the element at the current index, is returned.

Day 14 of 100 Days LeetCode Challenge

Question 7 of 75 - LeetCode Weekly Challenge