Product of Array Except Self ( #238 LeetCode )

 

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 <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

There are three ways to do this:

Method 1: 

1. Looping through elements and calculating the entire product of the array elements. 

2. Storing the elements in the output array by dividing the product of all elements by the number itself.

But, this is not recommended method from the question. Click here for whiteboard link.

Method 2: 

1. Finding the product of left elements of each element and storing it as leftProducts[].

2. Finding the product of right elements of each element and storing it as rightProducts[].

2. Storing the value of leftProducts * rightProducts as output array. 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int i = 0;
        int leftProducts[nums.size()], rightProducts[nums.size()];
        vector<int> output(nums.size());
        
        leftProducts[0] = 1;
        rightProducts[nums.size() - 1] = 1;
        for (i = 1; i < nums.size(); i++) {
            leftProducts[i] = nums[i -1] * leftProducts[i - 1];
        }
        
        for (i = nums.size() - 2; i >= 0; i--) {
            rightProducts[i] = nums[i + 1] * rightProducts[i + 1];
        }
        
        for (i = 0; i < nums.size(); i++) {
            output[i] = leftProducts[i] * rightProducts[i];
        }
        return output;
    }
};

But again, there is a space complexity issue because this leftProducts and rightProducts array used more space and it eventually led to 24.6 MB

Method 3: 

Gettign rid of the leftProducts and rightProducts array is the main focus here. 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        int i = 0;
        vector<int> output(len);
        
        output[0] = 1;
        for (i = 1; i < len; i++) {
            /* This calculates the left product of each element. */
            output[i] = nums[i -1] * output[i - 1];
        }
        
        int var = 1; 
        for (i = len - 1; i >= 0; i--) {
            /* 
             * This multiplies the left product 
             * with the next element by traversing 
             * from the right.
             */
            output[i] = output[i] * var;
            var = var * nums[i];
        }

        return output;
    }
}