Original problem – https://leetcode.com/problems/to-lower-case/
Problem definition
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]
Solution
It’s better to think about this problem by looking at both the input and the output at the same time. Let’s assume that we are trying to solve the set of integers: 1, 2, 3, 4. The answer to that would be 24, 12, 8, 6. Now let’s replace the result with actual math expressions (operations):
input | 1 | 2 | 3 | 4 |
output | 24 | 12 | 18 | 6 |
output (math) | 2*3*4 | 1*3*4 | 1*2*4 | 1*2*3 |
If we take a closer look we can understand that the result of a particular cell is a product of what we have on the left hand side and on the right hand side.
Now, if we think about how to get the product? We can iterate over the input and then create an inner loop for each cell and get a product except for self. Which gives us a quadratic complexity (O(n^2)). But taking into account the previous statement that the product of a particular cell is a product of left and right results we can achieve the goal simply in two iterations (calculating the product for all lefts and for all rights). And we can do it in only with 2 iteration which we can consider as a O(n). Let see how it works on example.
Note: the values that doesn’t have any result we have to replace with ‘1’ (the very first cell and the last cell)
input | 1 | 2 | 3 | 4 |
rights | 2*3*4 = 24 | 3*4=12 | 4 | 1 |
lefts | 1 | 1*1=1 | 1*2=2 | 1*2*3=6 |
result(rights*lefts) | 24*1=24 | 12*1=12 | 4*2=8 | 1*6=6 |
So let’s take a look at a code:
var prod = 1; result[nums.length - 1] = 1; for (var i = nums.length - 1; i > 0; i--) { int c = nums[i]; prod *= c; result[i - 1] = prod; }
We need to track the product of all previous calculations, so the way to do that is to iterate from the end to the start. We need to exclude the last element because it doesn’t have anything to the right. We put ‘1’ there not to mess up the final result when we will be multiplying its value with whatever we calculate processing all lefts. We calculate the product and put the result to the next cell (i -1).
Now we do the same but we start from the beginning in order to calculate all lefts:
prod = 1; for (var i = 1; i < nums.length; i++) { int c = nums[i - 1]; prod *= c; result[i] *= prod; }
We do the same. We track the product starting from the very first element. We start iterating from the second element since we have to ignore self-value (and it doesn’t have anything to the left). And the most crucial part here we do not simply assign the product to the cell but we multiply whatever we have in the result with the product result[i] *= prod;