Product of Array Except Self

Hi Geeks! Welcome to 100 Days Leetcode Challenge.

Day 2

Here is our given problem,

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

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

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Problem Explanation

Product of Array except self

In the above example of arr = [1, 2, 3, 4],

For every element, store the product of array elements except the element which you currently point.

That is, at element 1, store the product of array elements, except 1st element. Except 1, then remaining elements are 2, 3 and 4. Multiply these elements and store it in 1th element position, that’s 24.

At element 1, store the product of array elements, except 2nd element. Except 2, then remaining elements are 1, 3 and 4. Multiply these elements and store it in 2th element position, that’s 12.

At element 3, store the product of array elements, except 3rd element. Except 3, then remaining elements are 1, 2 and 4. Multiply these elements and store it in 1th element position, that’s 8.

At element 4, store the product of array elements, except 4th element. Except 4, then remaining elements are 1, 2 and 3. Multiply these elements and store it in 4th element position, that’s 6.

How to Approach this problem

Approach 1

The easier way to solve this problem by using two arrays, leftArray and rightArray.

leftArray

In leftArray store the product of element values from left. There is no element present left side of the index 0th position,. So put constant value 1 there.

At element 2, the product of left elements value is 1.

At element 3, the product of left elements value is 2.

At element 4, the product of left elements value is 6.

rightarray

In rightArray store the product of element values from right. There is no element present right side of the index (n-1)th position,. So put constant value 1 there.

Now just imagine, we have leftArray which contains all the product of left elements value except self and rightArray which contains all the product of right elements values except self.

Similarly for each other elements also. Multiply left[i] with right[i] to get our desired result of product of array elements except self.

But this won’t solve our problem, because, in our given question, they asked us to solve the problem in O(1) space complexity, that is constant space. So going to approach 2.

Approach 2

We need to reduce the space complexity. When you think deeply, you can able to agree that, we no need rightArray. We can use the simple variable, to do the rightArray task.

leftarray

    
    //left array which contains the product of elements to the right
    int[] leftArray = new int[nums.length];

    leftArray[0] = 1;
    for(int i=1;i<nums.length;i++)
    {
        leftArray[i] = leftArray[i-1] * nums[i-1];
    }

Right “R” Variable

  1. R contains the product of all the elements to the right
  2. For the element at index ‘length – 1’, there are no elements to the right, so the R would be 1.
        int R = 1;
        for(int i=nums.length-1;i>=0;i--)
        {
            // For the index 'i', R would contain the 
            // product of all elements to the right. We update R accordingly
            //Performing rightArray task using simple R variable, so we reducing O(n) extra space
            leftArray[i] = R * leftArray[i];
            R = R * nums[i];
        }

Solution

class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        //left array which contains the product of elements to the right
        int[] leftArray = new int[nums.length];
        
        leftArray[0] = 1;
        for(int i=1;i<nums.length;i++)
        {
            leftArray[i] = leftArray[i-1] * nums[i-1];
        }
        
        
        int R = 1;
        for(int i=nums.length-1;i>=0;i--)
        {
            // For the index 'i', R would contain the 
            // product of all elements to the right. We update R accordingly
            leftArray[i] = R * leftArray[i];
            R = R * nums[i];
        }
        
        return leftArray;
    }
}

Time Complexity : O(n)

Space Complexity : O(1) Constant space


Note:

If you like to join with me, please follow me via email. So that, whenever I solve problems and update here, you will get an email notification message.

Processing…
Success! You're on the list.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s