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 <= 105

Left and Right product lists

It’s much easier to build an intuition for solving this problem without division once you visualize how the differences products except self look like for each of the elements. So, let's take a look at an example array and the different products.

For every given index, ii, we will make use of the product of all the numbers to the left of it and multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index ii. Let’s look at a formal algorithm describing this idea more concretely.

Algorithm

  1. Initialize two empty arrays, L and R where for a given index i, L[i] would contain the product of all the numbers to the left of i and R[i] would contain the product of all the numbers to the right of i.

For the given array [4,5,1,8,2][4,5,1,8,2], the L and R arrays would finally be:

Complexity analysis

  • Time complexity: O(N) where N represents the number of elements in the input array. We use one iteration to construct the array L, one to construct the array R, and one last to construct the answer array using L and R.

Approach 2: O(1) space approach

Although the above solution is good enough to solve the problem since we are not using division anymore, there’s a follow-up component as well which asks us to solve this using constant space. Understandably so, the output array does not count towards the space complexity. This approach is essentially an extension of the approach above. Basically, we will be using the output array as one of L or R and we will be constructing the other one on the fly. Let's look at the algorithm based on this idea.

Algorithm

  1. Initialize the empty answer an array where for a given index i, answer[i] would contain the product of all the numbers to the left of i.

Complexity analysis

  • Time complexity: O(N) where N represents the number of elements in the input array. We use one iteration to construct the array L, one to update the array answer.

Full Stack Programmer, love to solve problem’s during free time.