Leetcode Reflections: #238, Product of Array Except Self

19 Oct 2023 -

TL;DR: Scroll to the bottom for the code

I didn’t solve this myself, but this is how it works. This is a variation on prefix sums and suffix sums. How would you know to think of such a thing? I didn’t, but I think the key clue would be that each element in the answer array is a result of some calculation of every element in the input array except itself. This exception can be rephrased to mean: multiply all of the elements before i (i.e. prefix) and multiply all the elements after i (i.e. suffix). With that in mind, here’s my understanding of the two concepts:

A prefix sum is the running sum of all the numbers up to and including the current number in the list from left to right. You’re on the right track if you see the phrase “running” and think “counter”. Our counter will naturally initialize to 0 since this is a summing operation. For example, in pseudocode:

prefix_sum = 0
nums = [1,2,3,4]
prefix_sums = [1,3,6,10]

A suffix sum is the same, except running in the opposite direction:

suffix_sum = 0
nums = [1,2,3,4]
suffix_sums = [10,9,7,4]

This problem differs in that we are looking for products, not sums. Right off the bat, since this is a multiplication operation, we can’t initialize to 0 or our counter will never produce anyhing. We’ll need to initialize it to 1 so the first operation will be a useful product.

A prefix product would look like this:

prefix_product = 1
nums = [1,2,3,4]
prefix_products = [1,2,6,24]

And a suffix product would like like this:

suffix_product = 1 nums = [1,2,3,4] suffix_products = [24,24,12,4]

However, we can already tell that this is not quite right. We need to factor in that as we calculate the prefix/suffix that we exclude nums[i] for our given product[i].How do we exclude a given number from our product calculation? We could divide it out of the final list (e.g. answer[i] /= nums[i]), but that’s explicitly not allowed.

The best solution was a bit difficult for me to wrap my head around: we need to initialize all of our answers to 1.

prefix_product = 1
nums = [1,2,3,4] 
initial_prefix_products = [1,1,1,1]
final_prefix_products = [1,1,2,6]

I’ll admit, this is not very intuitive without getting into the code. Think of it this way: at first we were initializing each answer[i] to nums[i], to be multiplied by each other element in the array (the running prefix). If we initialize to 1, we have a simple way to avoid including the current number in the prefix/suffix calculation. Rather than multiply by the current number, we multiply our current running product by the current corresponding element in the answer array. Since we initialized all of those value to 1 the running product will be unchanged, in effect excluding the current element nums[i]. After we commit this product to the answer array, we can update the running product with the current elements in nums so the next cycle has the correct running product. Said more concisely: We update the answers array at i with the current running product, and then we update it for the next cycle to include the current element from nums at i.

Let’s look at suffix product now:

suffix_product = 1
nums = [1,2,3,4]
initial_prefix_products = [1,1,1,1]
suffix_products = [12,12,4,1]

Our answer still doesn’t look right though, and that’s because we are still only accounting for one side of i for each running product. Let’s combine the two, in pseudcode:

prefix_product = 1
nums = [1,2,3,4] 
init_answers = [1,1,1,1]
~calculation~
intermediate_prefix_answers = [1,1,2,6]

suffix_product = 1
nums = [1,2,3,4]
intermediate_prefix_answers = [1,1,2,6]

final_combined_answer = [24,12,8,6]

This is a little easier to read in the actual code in terms of looped instructions: - initialize our answer array and running products - loop over the length of our input array - update the answer at i with the answer at i times the running product - update the running product with the running product times the current number at i

You could do this with two consecutive loops, calculating first the prefix products and then the suffix products or vice versa. This would give you a time complexity of O(2N), which is really just O(N) and perfectly acceptable. However you can do this in one loop, traversing from both ends of the array at once. You can do this in Python by by subtracting length-i-1 to get the end of the array, decrementing with each pass. However, I know a little trick that looks much cooler: bitwise negation.

In binary, bitwise negation is essentially flipping all the 0s to 1s and 1s to 0s. In Python, negative binary numbers are represented with leading 1s. So if you have a 0, and you flip all of the bits, you have 1, except with leading 1s, which means -1. Python Lists interpret negative indices as starting from the end of the list. So nums[-1] is actually the last element. The specifics of Python integers and bitwise operators are a bit more complicated than that, so check out the docs on python bitwise operators, but basically this let’s us get the mirror position of a given index at the end of a list.

Anyways, that’s my understanding of this problem and my tiny contribution to it. I didn’t get it on my own, so I had to write all of this out, and I hope it helps somebody else down the line.

Solution in Code:

class Solution:

    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = [1] * len(nums)
        prefix_product = 1
        suffix_product = 1
        for i in range(len(nums)):
            answer[i] *= prefix_product
            prefix_product = prefix_product * nums[i]
            answer[~i] *= suffix_product
            suffix_product = suffix_product*nums[~i]
        return answer