Daily Coding Problem Write-up
Day 2— Product of Array Except Self
Given an array nums
of n integers where n > 1, return an array output
such that output[i]
is equal to the product of all the elements of nums
except nums[i]
.
O(n) runtime, O(n) space
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size(); // Initialize vectors (i.e. arrays) of n 1’s vector<int> result(n, 1);
vector<int> fromBegin(n, 1);
vector<int> fromEnd(n, 1); for(int i=1; i<n; i++){
fromBegin[i] = fromBegin[i-1] * nums[i-1];
fromEnd[i] = fromEnd[i-1] * nums[n-i];
}
for(int i=0; i<n; i++){
result[i] = fromBegin[i] * fromEnd[n-1-i];
}
return result;
}
Explanation:
Let’s take nums = [1,2,3,4,5]
as an example.
After the 1st pass,
fromBegin = [1, 1x1, 2x1x1, 3x2x1x1, 4x3x2x1]
fromEnd = [1, 5x1, 4x5x1, 3x4x5x1, 2x3x4x5x1]
Notice they are look like mirror images of one another, i.e. each array contains half the product needed. Therefore, in order to construct the result array, we have to combine the fromBegin
and fromEnd
arrays like so:
result[i] = fromBegin[i] x fromEnd[n-1-i];
More specifically,
result[0] = fromBegin[0] x fromEnd[5–1–0] = (1) x (2x3x4x5x1) = 2x3x4x5 (i.e. product of all elements except 1)
result[1] = fromBegin[1] x fromEnd[5–1–1] = (1x1) x(3x4x5x1) = 1x3x4x5 (i.e. product of all elements except 2)
result[2] = fromBegin[2] x fromEnd[5–1–2] = (2x1x1) x(4x5x1) = 1x2x4x5 (i.e. product of all elements except 3)
so on and so forth…
O(n) runtime, O(1) space (if we don't count the output array)
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, 1);
int fromBegin = 1;
int fromEnd = 1;
for(int i=1; i<n; i++){
fromBegin *= nums[i-1];
result[i] *= fromBegin;
fromEnd *= nums[n-i];
result[n-1-i] *= fromEnd;
}
result[0] = fromEnd;
result[n-1] = fromBegin;
return result;
}
Space Optimization:
If we look at how we calculated the result
array from fromBegin
and fromEnd
arrays, we'll find that each element in fromBegin
and fromEnd
were actually only used once. This means we don't have to store the intermediate values calculated in the fromBegin
and fromEnd
arrays.
More specifically, following the same example with nums = [1,2,3,4,5]
, we can first initialize fromBegin
and fromEnd
as 1, and result as [1,1,1,1,1]
, then:
In the first iteration,
fromBegin = 1 x 1
fromEnd = 5 x 1
At this instance, fromBegin
can already be multiplied into result[1]
and fromEnd
can already be multiplied into result[5–1–1]
.
In the second iteration,
fromBegin = 1 x 1 x 2
fromEnd = 4 x 5 x 1
At this instance, fromBegin
can already be multiplied into result[2]
and fromEnd
can already be multiplied into result[5–1–2]
.
After the first pass, all values in result are ready except the first and the last ones. Right now,
fromBegin = 1 x 1 x 2 x 3 x 4
fromEnd = 2 x 3 x 4 x 5 x 1
Meaning fromBegin
is exactly the value of result[4]
and fromEnd
is exactly the value of result[0]
! Therefore, we can simply do:
result[0] = fromEnd;
result[n-1] = fromBegin;
Note:
- This is one of those problems where you just have to stare at the problem long enough until you find the right pattern. Not fun.