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]

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.)

Contents

Solution 1 - using prefix and postfix arrays

In this approach, what we are going to do is, build two separate arrays prefix array and postfix array and populate these array with prefix product values from left to right into prefix array and right to left into postfix array.

Once we have prefix array and postfix array, then the product value of entire array except the element at index i will be the product of the values prefix[i-1] and postfix[i+1], and for the edge case scenarios where i is either 0 or end of array we can take these values as 1.

Java
ans[i] = (i==0 ? 1 : prefix[i-1]) * (i==nums.length-1 ? 1 : postfix[i+1]);

Consider an example, nums = [1, 2, 3, 4]

  • We will create prefix and fill it with prefix product values:
    Java
    for(int i=0; i<nums.length; i++) {
      prefix[i] = nums[i] * (i ==0 ? 1 : prefix[i-1]);
    }
    prefix array will look like this [1, 2, 6, 24]
  • We will create postfix and fill it with postfix product values:
    Java
    for(int i=nums.length -1; i>=0; i--) {
      postfix[i] = nums[i] * (i==nums.length-1 ? 1 : postfix[i+1]);
    }
    postfix array will look like this [24, 24, 12, 4]
  • Once we have the prefix and postfix arrays, then if we want to compute product of entire array except self, then we should take the product of all values from left side of array before current element, which we can find it from prefix array at i-1th index and product of all values from right side of array after current element, which we can find it from postfix array at i+1th index.
    Java
    int[] ans = new int[nums.length];
    for(int i=0 ;i< nums.length; i++) {
        ans[i] = (i==0 ? 1 : prefix[i-1]) * (i == nums.length-1 ? 1 : postfix[i+1]);
    }
    ans array
    index prefix postfix ans
    0 1 24 1 (because i== 0) * 24 = 24
    1 2 24 1 * 12 = 12
    2 6 12 2 * 4 = 8
    3 24 4 6 * 1 (because i== nums.length -1) = 6

Java
public class ProductOfArrayExceptSelf {

    /**
      * Using prefix and postfix arrays
      */
    static int[] usingPrefixAndPostfixArrays(int[] nums) {
        int[] prefix = new int[nums.length];
        int[] postfix = new int[nums.length];
        for(int i=0; i<nums.length; i++) {
            prefix[i] = nums[i] * (i ==0 ? 1 : prefix[i-1]);
        }
        for(int i=nums.length -1; i>=0; i--) {
            postfix[i] = nums[i] * (i==nums.length-1 ? 1 : postfix[i+1]);
        }

        int[] ans = new int[nums.length];
        for(int i=0 ;i< nums.length; i++) {
            ans[i] = (i==0 ? 1 : prefix[i-1]) * (i == nums.length-1 ? 1 : postfix[i+1]);
        }
        return ans;
    }

}
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input array nums.
Space complexity: O(n) for the prefix and postfix arrays.

Solution 2 - using prefix and postfix arrays approach without really creating them (Answer to the follow-up question)

In this approach, we are going to use the same solution as we saw in previous approach, but without really creating prefix and postfix array.

We are going to create the ans array and use that to store the prefix and postfix product values directly into this array:

  • One thing that we do differently in this case is, instead of storing the prefix product values, we compute prefix product and store that at the next index. This is because we will be using product until index i at i+1th index from prefix product.

    For example say if the input array has elements like this [0......k, k+1,......n] when we compute prefix product at 0, that will be used at index 1 and similarly the prefix product until k will be used at k+1.

    For example, if the input array is nums = [1, 2, 3, 4], then we will fill the ans like this:

    ans array prefix
    index nums ans
    0 1 1 (we will place 1 here, as it has no impact on product)
    1 2 nums[i-1] * ans[i-1] = 1 * 1 = 1
    2 3 2 * 1 = 2
    3 4 3 * 2 = 6

    If you notice ans array after prefix values calculated and placed at thr right indexes, last element in the ans array will be the right value for that index (product of all except self).

  • In the next step, we will start from right to left from index nums.length-2 to index 0 and compute the postfix and multiply that with current element in ans array.

    ans array after postfix
    index nums ans (before prefix) ans (after prefix)
    0 1 1 postfix = 12 * (nums[i+1]) = 12 * 2 = 24
    ans[i] * postfix = 1 * 24 = 24
    1 2 1 postfix = 4 * (nums[i+1]) = 4 * 3 = 12
    ans[i] * postfix = 1 * 12 = 12
    2 3 2 postfix = 4 (nums[i+1])
    ans[i] * postfix = 2 * 4 = 8
    3 4 6 6 (we dont touch it, as it is already computed correctly in prefix array)

Java
public class ProductOfArrayExceptSelf {


    /**
      *
      * we are going to use answer array itself to store prefix array values, 
      * then multiply those with postfix product
      */
    static int[] usingPrefixAndPostfixProductMemoryOptimized(int[] nums) {

        int[] ans = new int[nums.length];
        // building prefix product values and placing them at i+1,
        // as this is where we would need i.....k product at k+1 (th) index
        ans[0] = 1;
        for(int i=1; i<nums.length; i++) {
            ans[i] = nums[i-1] *ans[i-1];
        }

        // compute post fix and multiply that with ans[i]
        int postfix = 1;
        for(int i=nums.length -2; i>=0; i--){
            postfix = postfix * nums[i+1];
            ans[i] = ans[i] * postfix;
        }
        return ans;
    }


}
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input array nums.
Space complexity: O(1) if we dont consider ans output array.

Above implementations source code can be found at GitHub link for Java code