I came across an interesting question, so thought of sharing this!

Question : 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 1:

Input:  [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:

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

Problem link: Product of Array Except Self

Lets begin with the straight forward approach (i.e. Brute force solution).

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int product = 1;
        vector<int> output;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i != j)
                    product = product * nums[j];
            }
            output.insert(output.begin() + i, product)
        }
        return output;    
    }
};

The time complexity for this solution is O(nĀ²) so it’s not much efficient. Another idea that’s coming in my mind is to obtain product for all the elements in the array and divide by the number that shouldn’t be included in the array. Let’s try and see what happens.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> output;
        int product = 1;
        for (int i = 0; i < nums.size(); i++) {
            product = product * nums[i];
        }
        for (int i = 0; i < nums.size(); i++) {
            output.insert(output.begin() + i, product/nums[i]);
        }
        return output;
    }
};

This looks good but what if nums[i] = 0? This seems to be an important edge case where division by zero exception will occur. So, to avoid this, we can think of two use cases -

  1. One 0 exists in the input array.
  2. More than one 0 exists in the input array.

For the second case i.e. 0 existing more than once, we can say the output array will all elements equal to zero.

But, for the first case i.e. if we have only one 0, then we will only get output for that item only.

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

This can be solved easily by using a zero counter and if else condition.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> output;
        int product = 1, count_zero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                count_zero++;
            } 
            else {
                product *= nums[i];
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            // In case one element in the input array is 0.
            if (count_zero == 1) {
                if (nums[i] == 0)
                    output.insert(output.begin() + i, product);
                else
                    output.insert(output.begin() + i, 0);
            }
            // In case more than one element is 0.
            else if (count_zero > 1) {
                output.insert(output.begin() + i, 0);
            } 
            // In rest of cases, i.e. count_zero = 0.
            else {
                    output.insert(output.begin() + i, product/nums[i]);
            }
        }
        return output;
    }
};

Yayy!! The time complexity for this solution is O(n), this is much more efficient than our very first approach.

Another way to solve the problem without divison is to observe the pattern, maintain a left multiplication array and store right multiplication value.

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

Approach:

Left = [1,2,6,24]
Output[i] = Left[i-1] * Right multipication

So basically, we need to obtain a left multiplication array and store their right multiplication array in a variable.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> output;
        // To obtain a left multiplication array
        int left_product = 1; 
        for (int i = 0; i < nums.size(); i++) { 
            left_product = left_product * nums[i];
            output.insert(output.begin()+i, left_product);
        }
        int right_product = 1; // to store right multipication
        for (int i = nums.size()-1; i > 0; i--) {
            output[i] = output[i-1] * right_product;
            right_product = right_product * nums[i];
        }
        // Edge case condition 
        // output[0] = output[0-1]*right_product
        output[0] = right_product;

        return output;
        }
};

  1. Time Complexity: O(n), where n is the number of elements.

  2. Space complexity: O(1) since we are not using any extra data structure for computation.

    NOTE: The output array does not count as extra space for space complexity analysis.

Thanks for reading!