Product of Array Except Self

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

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

public int[] productExceptSelf(int[] nums) {
    int[] result = new int[nums.length];
    int prod = 1;
    for(int i = 0; i < nums.length; ++i){
        result[i] = prod;
        prod *= nums[i];
    }

    prod = 1;
    for(int i = nums.length - 1; i >= 0; --i){
        result[i] *= prod;
        prod *= nums[i];
    }

    return result;
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  const result = new Array(nums.length).fill(1);
  let prod = 1;

  for (let i = 0; i < nums.length; ++i) {
    result[i] *= prod;
    prod *= nums[i];
  }

  prod = 1;
  for (let i = nums.length - 1; i >= 0; --i) {
    result[i] *= prod;
    prod *= nums[i];
  }

  return result;
};

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = [1] * len(nums)
        prod = 1

        for i in range(len(nums)):
            result[i] *= prod
            prod *= nums[i]

        prod = 1
        for i in range(len(nums) - 1, -1, -1):
            result[i] *= prod
            prod *= nums[i]

        return result

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result(nums.size(), 1);
        int prod = 1;

        for (int i = 0; i < nums.size(); ++i) {
            result[i] *= prod;
            prod *= nums[i];
        }

        prod = 1;
        for (int i = nums.size() - 1; i >= 0; --i) {
            result[i] *= prod;
            prod *= nums[i];
        }

        return result;
    }
};

Time/Space Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Explanation:

First notice that we have been given a lot of restrictions by the problem statements, but also those restrictions can lead us to the optimal solution. The trick to solving this problem is in the problem statement and that is using prefix and suffix products of array. What are suffix and prefix products? Prefix product is the product of all elements in array that occur before certain index (e.g. prefixProduct[i] = nums[0] * nums[1] * nums[2] * ... * nums[i-1]) while the suffix products is the product of all elements occuring after specific index (e.g. e.g. suffixProduct[i] = nums[i+1] * nums[i+2] * nums[i+3] * ... * nums[nums.length-1]). So how do we get the product of all elements except for the current element? It's easy, it's just the product of Prefix and Suffix products result[i] = prefixProduct[i] * suffixProduct[i]. Notices that we don't have to keep prefixProduct and suffixProduct array (thus bringing the space complexity to O(1)) we can just calculate them as we go. We start with neutral element for the multipication operation (prod = 1) and we first iterate from left to right each time multiplying the current prod with the current element which becomes the prefixProduct of the next element. In the second loop we iterate from the right to left to calculate the suffixProduct doing the same multiplication prod *= nums[i]. At the end we just return the result array. Notice that prefix/suffix sums or products (also seen in Range Query Sum Immutable) come in handy in many array problems and keep them in your arsenal of algos to use when faced with array input.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​