Given an integer array
nums, return an array
answer such that
answer[i] is equal to the product of all the elements of
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]
Input: nums = [-1,1,0,-3,3]
2 <= nums.length <= 105
-30 <= nums[i] <= 30
- The product of any prefix or suffix of
numsis guaranteed to fit in a 32-bit integer.
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.
- Initialize two empty arrays,
Rwhere for a given index
L[i]would contain the product of all the numbers to the left of
R[i]would contain the product of all the numbers to the right of
- We would need two different loops to fill in values for the two arrays. For the array
L, L would be
1since there are no elements to the left of the first element. For the rest of the elements, we simply use L[i]=L[i−1]∗nums[i−1]. Remember that
L[i]represents the product of all the elements to the left of the element at index i.
- For the other array, we do the same thing but in reverse i.e. we start with the initial value of
1in R[length−1] where length is the number of elements in the array and keep updating
R[i]in reverse. Essentially, R[i]=R[i+1]∗nums[i+1]. Remember that
R[i]represents the product of all the elements to the right of the element at index i.
- Once we have the two arrays set up properly, we simply iterate over the input array one element at a time, and for each element at the index
i, we find them
product except selfas L[i]∗R[i].
For the given array [4,5,1,8,2][4,5,1,8,2], the
R arrays would finally be:
- 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.
- Space complexity: O(N) used up by the two intermediate arrays that we constructed to keep track of the product of elements to the left and right.
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
R and we will be constructing the other one on the fly. Let's look at the algorithm based on this idea.
- Initialize the empty
answeran array where for a given index
answer[i]would contain the product of all the numbers to the left of
- We construct the
answerarray the same way we constructed the
Larray in the previous approach. These two algorithms are exactly the same except that we are trying to save up on space.
- The only change in this approach is that we don’t explicitly build the
Rarray from before. Instead, we simply use a variable to keep track of the running product of elements to the right and we keep updating the
answerarray by doing answer[i]=answer[i]∗R. For a given index
answer[i]contains the product of all the elements to the left and
Rwould contain the product of all the elements to the right. We then update
- 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.
- Space complexity: O(1) since don’t use any additional array for our computations. The problem statement mentions that using the answer array doesn’t add to the space complexity.