Product of Array Except Self

Problem: Given an array nums of n integers,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without using division. 

Example:

Input:  [2, 3, 4, 5]
Output: [60, 40, 30, 24]

Approach: If division was allowed then this problem was straight forward. Calculate the product of all the elements in the array and then divide it by current number:

output[i] =  productOfElement / nums[i]

But given we can't use division, we need to think differently. Let's see what we can do. It is easy to understand that:

Product_Of_All_Elements_Except_Current_Element = Product_Of_All_Elements_Left_Of_Current_Element  * Product_Of_All_Elements_Right_Of_Current_Element

Right! That means if we can calculate Product_Of_All_Elements_Left_Of_Current_Element and Product_Of_All_Elements_Right_Of_Current_Element efficiently, we can calculate Product_Of_All_Elements_Except_Current_Element efficiently. 

If you see these are cumulative calculations. What we can do is have 2 arrays: 

1. LeftProductArray where LeftProductArray[i] = Prodcuct of nums[0] to nums[i-1] (Product_Of_All_Elements_Left_Of_Current_Element). We can fill this array easily:
1. LeftProductArray[0] = 1
2. LeftProductArray[i] = nums[i-1] * LeftProductArray[i-1] // i = 1 to n - 1
2. RightProductArray where RightProductArray[i] = Prodcuct of nums[i+1] to nums[n-1] (Product_Of_All_Elements_Right_Of_Current_Element). We can fill this array similar to above array easily:
1. RightProductArray[n-1] = 1
2. RightProductArray[i] = RightProductArray[i+1] * nums[i+1] // i = n - 2 to 0

Now we can fill our output array easily i.e.

Output[i] = LeftProductArray [i] * RightProductArray[i]

This will work and it will solve our problem in linear time but if you see it is taking extra space. Let's see how we can optimize it:

1. Instead of taking extra LeftProductArray, we can use Output array itself so in the first loop we will fill Output array instead of LeftProductArray similarly:
1. Output[0] = 1
2. Output[i] = Output[i-1] * nums[i-1]
2. If you see we have already reduced the space by eliminating the use of LeftProductArray but we are still using O(n) extra space. Can we do something about RightProductArray? Yes, if you see all these calculations are cumulative so instead of having an array, we can just use one variable say CurrRightProduct and store the products of right elements in it so our second and final loop will do following steps:
1. CurrRightProduct = 1
2. Output[i] = Output[i] * CurrRightProduct // Output[i] already have Product_Of_All_Elements_Left_Of_Current_Element and we are multiplying it will CurrRightProduct which contains Product_Of_All_Elements_Right_Of_Current_Element 
3. CurrRightProduct = CurrRightProduct * nums[i] // storing this for next iteration which will be for (i - 1)th index.

That's all!

 

Implementation in C#:

        public int[] ProductExceptSelf(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return nums;

        }

        int[] result = new int[length];

        result[0] = 1;

        for (int i = 1; i < length; ++i)

        {

            result[i] = result[i - 1] * nums[i - 1];

        }

        int rightProduct = 1;

        for (int i = length - 2; i >= 0; --i)

        {

            rightProduct *= nums[i + 1];

            result[i] *= rightProduct;

        }

        return result;

    }

Complexity: O(n)