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

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

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

Solution 1 - using 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, 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. 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: 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: 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-1^th index and product of all values from right side of array after current element, which we can find it from postfix array at i+1^th index. 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

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.

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+1^th 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)

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

Follow up:

Contents

Complexity Analysis:

Complexity Analysis: