238. Product of Array Except Self: O(1) Space

Since the question asks about everything multiplied prior to and after current index, we natually think of some sort of prefix sum. However, the direct way of building prefix and postfix product arrays will not fit in the follow-up O(1) space constraint.

We then think if it is possible to only store prefix and postfix as constants and we somehow update while iterating. But that can also fail for an array that contains zeros:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

prefix constant will be: -1 → -1 → 0 → 0 → 0.
postfix constant will be: 0 ← 0 ← 0 ← -9 ← 3.
For example, 0 ← -9, we have no way to know -9 given nums[3] = -3 if we only know the 0 and the prefix constant.

I failed to utilize the ample O(n) space of the output. (ref: How is O(1) Space Complexity Defined in LeetCode)

According to the question, we need to “return an array answer,” which means we need a new array of length n; the key is that this array will not be counted to the space complexity under LeetCode’s definition.

This means that we have exactly 1 free O(n) array which will be used as the result.

Things get easier given this free array. We would intuitively try to make use of this array as a prefix product array, in some way.

For a general example, result[i] will rely on everything multiplied within nums[:i] and nums[i+1:]. This leads us to wanting a prefix-tracking constant (i.e., the multiplicative result of everything prior) and a postfix-tracking constant (i.e., everything after).

Ideally, we would just grab the prefix constant and the postfix constant, multiply them, and it will be result[i]. However, we can’t reliably find a way to know the current prefix constant without traversing from the left, nor the postfix without from the right. Therefore we need to think about a way to sequentialize the 2 traversals without breaking things.

Since it’s multiplicative, it is possible for us to “multiply everything from the left without immediately needing everything from the right” - we can just do the second multiplication later.

We will traverse from left to right while keeping track of the prefix constant as well as partially (for a*b, we are now only multiplying a for now) updating our result array.

After that, we do the similar by traversing from right to left while keeping track of the postfix constant as well as finishing the *b operation within a*b, and we are golden!

 1class Solution:
 2    def productExceptSelf(self, nums: List[int]) -> List[int]:
 3        n = len(nums)
 4        result = [1] * n
 5        pre = 1
 6        post = 1
 7
 8        for i in range(n):
 9            result[i] = pre
10            pre *= nums[i]
11
12        for i in range(n - 1, -1, -1):
13            result[i] *= post
14            post *= nums[i]
15
16        return result