Product of Array Except Self

November 2021

Summary

A Python implementation of Leetcode 238 – Product of Array Except Self. It runs in big-O of \(n\), in both time & space.

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).

Constraints

• \(2 <= nums.length <= 10^5\)
• \(-30 <= nums[i] <= 30\)

Naive Approach—\( O(n^2) \)

In Example 1, the input array is nums = [1,2,3,4] and the expected output is [24, 12, 8, 6]. One procedure we could execute to obtain that result would be to iterate through the elements of the input array such that at each iteration the iterated element itself is suppressed, we then iterate again through the remaining elements and multiply them together. This method would yield the following series of operations:

\( (index, key) \rightarrow product( \forall n \in \{nums\} \setminus nums[i] ) = productExceptSelf_i \)
\( (i=0, k=1) \rightarrow 2\times3\times4 = 24 \)
\( (i=1, k=2) \rightarrow 1\times3\times4 = 12 \)
\( (i=2, k=3) \rightarrow 1\times2\times4 = 8 \)
\( (i=3, k=4) \rightarrow 1\times2\times3 = 6 \)

Below is an implementation of this idea in code.

# naive approach
nums = [1, 2, 3, 4]
output = []
for i in range(len(nums)):
    product_except_self = 1  # start a running product
    for j in range(len(nums)):
        if j == i:  # ignore the element from the outer loop
            pass
        else:
            product_except_self = product_except_self * nums[j]
    output.append(product_except_self)
print(output)  # [24, 12, 8, 6]

Although this algorithm produces the correct output, it’s inefficient, as it needs to go through a double for loop to compute the result: the outer loop to suppress the element, and the inner loop for the running product of the remaining elements. This routine implies \( O(n^{2}) \) time complexity. Fourtunately, that can be improved.

Note however, that using the division operator to complete this task is not permitted. If that were not the case, deriving the solution would be trivial: compute the product of all elements then divide it by each element—with \( O(n) \) complexity.

# using division
nums = [1, 2, 3, 4]
total_product = 1
for n in nums:
    total_product *= n  # O(1) memory
output = [int(total_product/n) for n in nums]  # O(n) memory
print(output)  # [24/1, 24/2, 24/3, 24/4] == [24, 12, 8, 6]

Prefix & Suffix Approach—\( O(n) \)

When we remove each element—while iterating through the outer loop—we are effectively splitting the input array in two parts: one to the left of the element, called the prefix; and another to the right of the element, called the suffix. If we multiply an element’s prefix times its suffix, we obtain the product of all elements except itself.

To really use this idea though, first we need to take care of two edge cases. Namely, how to define the prefix of the first element, and the suffix of the last element. Technically, both of these are null, but it’ll be more convenient if we resolve this by padding both sides of the array with the identity element [of multiplication] (i.e., one); nums = [1, 2, 3, 4] would therefore become nums = [1, 1, 2, 3, 4, 1]. This new procedure would look like this:

\( (index, key) \rightarrow prefix(i) \times suffix(i) = productExceptSelf_i \)
\( (i=0, k=1) \rightarrow 1\times (2\times3\times4\times1) = 1\times24 = 24 \)
\( (i=1, k=2) \rightarrow (1 \times 1) \times (3\times4\times1) = 1\times12 = 12 \)
\( (i=2, k=3) \rightarrow (1 \times 1 \times 2) \times (4\times1) = 2\times4 = 8 \)
\( (i=3, k=4) \rightarrow (1 \times 1 \times 2 \times 3) \times 1 = 6\times1 = 6 \)

Grouping the total product by prefix and suffix is a powerful idea, because it leads to the realization that computing them separately is much more efficient. Specifically, the array of prefixes can be computed in a single \( O(n) \) pass using a running product—and the same is true for the array of suffixes. Then, a final \( O(n) \) pass would be required to compute the element-wise multiplication between prefix and suffix; as shown below.

# prefix
prefix = [1]  # first element's prefix
for n in nums[:-1]:
    prefix.append(prefix[-1] * n)
print(prefix)  # [1, 1, 2, 6]

# reverse suffix
suffix = [1]  # last element's suffix
for i in range(len(nums)-1):
    suffix.append(suffix[-1] * nums[~i])
print(suffix)  # [1, 4, 12, 24]

# product except self
output = []
for i in range(len(prefix)):
    output.append(prefix[i] * suffix[~i])
print(output) [24, 12, 8, 6]

Improving Memory by a Factor of 3

We’ve hit a limit on time complexity, but the memory footprint can still be improved. Note that under Big O notation the high-level idea is to supress details like constant factors and lower-order terms, and to focus instead on running times as a function of input-size growth. That is to say, \( O(n) \) and \( O(kn) \) share the same growth asymptotes. However, in practical systems, these ignored details can still have significant impact, enough to merit further optimization.

As it stands, the algorithm requires three \( O(n) \) data structures to hold the three arrays and produce an output: prefix, suffix and output—although a single one would suffice. To see it, let’s begin by initializing the output array and using it to store the results from the first pass, i.e., prefix values. Next comes the second pass, which instead of using another array, uses a \( O(1) \) pointer—suffix—to store all intermediate suffix values. At each iteration of the second pass output[i] is overwritten as output[i] = output[i] * suffix and suffix is updated.

In other words, the pass for suffix is executed in-place over the same data structure, which is then returned. After adding these improvements and a few extra lines to process and test cases, the implementation is complete.

# product_except_self.py

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        output = [1]  # first element's prefix
        for n in nums[:-1]:
            output.append(output[-1] * n)

        suffix = 1  # last element's suffix
        for i in range(len(nums) - 1, -1, -1):  # [start, stop), neg stride
            output[i] *= suffix
            suffix *= nums[i]
        return output

if __name__ == "__main__":
    solution = Solution()
    # test cases: [[nums], [output]]
    test_cases = [
        [[1, 2, 3, 4], [24, 12, 8, 6]],
        [[-1, 1, 0, -3, 3], [0, 0, 9, 0, 0]],
    ]
    # testing
    for case in test_cases:
        nums, output = case
        assert solution.productExceptSelf(nums) == output
    print("Success! All test cases have passed.")

$ python3 .../product_except_self.py
Success! All test cases have passed.