Blind 75.04 - Product of Array Except Self

Product of array except self.

Problem description

Taken directly from LeetCode.

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 <= \(10^5\)
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Solution type

Caching.

Solution

An intuitive but inefficient solution would be something like this. out starts as a vector of ones, then in a nested for loop we multiply each element in nums to each element in out that isn’t at the same index:

vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> out(nums.size(), 1);

    for (size_t i = 0; i < nums.size(); ++i) {
        for (size_t j = 0; j < nums.size(); ++j) {
            if (i != j) {
              out[i] *= nums[j];
            }
        }
    }

    return out;
}

The problem description stipulates \(O(n)\) time, so we need to figure out how to improve on this. If we think about where that time complexity is coming from, we are doing \(O(n)\) operations (multiplications) for \(O(n)\) elements. We need to do something for all \(n\) elements in nums, so the next thing to think of is how to reduce the \(O(n)\) operations down to \(O(1)\) operations.

Consider the array [1,2,3,4]. The way I thought about this (and even though I’ve done this one a long time ago, it still took some effort to figure this out) was as follows.

Instead of naively constructing each element one by one, we could think of our naive solution¹ as going through nums and naively multiplying each element to every output position. Iteration 1:

• out[0] = X * ...
• out[1] = 1 * ...
• out[2] = 1 * ...
• out[3] = 1 * ...

Iteration 2:

• out[0] = X * 2 * ...
• out[1] = 1 * X * ...
• out[2] = 1 * 2 * ...
• out[3] = 1 * 2 * ...

Iteration 3:

• out[0] = X * 2 * 3 * ....
• out[1] = 1 * X * 3 * ....
• out[2] = 1 * 2 * X * ....
• out[3] = 1 * 2 * 3 * ....

Iteration 4:

• out[0] = X * 2 * 3 * 4
• out[1] = 1 * X * 3 * 4
• out[2] = 1 * 2 * X * 4
• out[3] = 1 * 2 * 3 * X

You can see that we’re reusing numbers in our multiplication. If we had a fifth element out[4], we already know that we’ll need to multiply by 1 * 2 * 3 for that corresponding output. If we had 100 numbers, we’d know from computing the product for the 50th number what numbers we’d need to multiply to get the 51st number (that is, the 1st-49th numbers as well as the 52nd-100th numbers). I’m being a bit rough around the corners, I hope the general idea is getting across at least? This is how it came together in my head; I’m just trying to be as illustrative as possible.

The clearest way to put it is that we are building array prefixes and suffixes. For any given index, the prefix is the product of all elements in nums that come before that index and the suffix is the product of all elements in nums that come after that index. As the index value increases, the prefix accumulates more elements. I think it’s easier to think of accumulating the suffix going backwards: that is, start at nums.size() - 1 and go down to 1².

The trick to saving time is that we will now only do two multiplications per output element: one for the prefix built up to that element, and one for the suffix built down to that element. Basically, we will build the prefix going from index 0 to index nums.size() - 2, and for each iteration that we’re building the prefix, we’ll multiply the output element corresponding to that iteration by the prefix. Same idea with the suffix except we start at the back and go to the front.

The solution below is \(O(n)\) time and \(O(1)\) space. I think there’s a way to reduce some constants in the time complexity (e.g. by combining the for loops) but I don’t know if anyone would be picky enough to make you do that in an actual interview.

vector<int> productExceptSelf(vector<int>& nums) {
    int prefix = 1, suffix = 1;
    vector<int> out(nums.size(), 1);

    for (size_t i = 1; i < nums.size(); ++i) {
        prefix *= nums[i - 1];
        out[i] *= prefix;
    }
    for (size_t i = nums.size() - 1; i > 0; --i) {
        suffix *= nums[i];
        out[i - 1] *= suffix;
    }

    return out;
}

Note that we don’t need to write separate conditional blocks for 0 or negative values; those cases are handled by the general solution already.

This is fundamentally a caching problem. Instead of recomputing the suffix and prefix for every output value, we store what we have so far and use it to get the other computed values.

1. I mean, this is how my naive solution is written. But you could easily rewrite it so that it multiplies all the numbers for one output, then moves on to the next output elt, etc, and i think that’s how most people would do it. ↩

2. 1, not 0, since the suffix will never include the element at index 0. ↩