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.