Product of Array Except Self

Intuition

• Whenever you have something akin to all elements except x, this could be a candidate for a Prefix and Postfix type problem.
• The solution with O(1) space besides the space needed to store the result uses a clever Trick in which we know the first index of the result will be the postfix of the product of all numbers up until that point (so postfix[i + 1]). Therefore, it follows that if we place 1 in that first index, a postfix multiplying up until that point will be the same as postfix[i + 1] (the optimal solution).
• That is why in O(1) Space, we start the first for loop from 1.
• In the same way, when you do answer[i - 1] * nums[i - 1], you are setting the first element following the one to be the first element from your nums array and multiplying thereafter.

Complexity

Runtime

$O(N)$ to compute against prefix and postfix in 3 passes.

Space

$O(1)$ if you use the given input array as your space to store the postfix and a variable to store the prefix (if we don’t include the space needed to return the result).

Code

O(1) Space

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n
 
        for i in range(1, n):
            answer[i] = answer[i - 1] * nums[i - 1] # Note that the answer[0] remains the same (is the last postfix)
        
        postfix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= postfix # Note that the answer[n - 1] remains the same (is the last prefix)
            postfix *= nums[i] # Getting the postfix on each iteration
        
        return answer

O(N) Space

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix = [0] * n
        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = nums[i] * prefix[i - 1]
 
        postfix = [0] * n
        postfix[-1] = nums[-1]
        for i in range(n - 2, -1, -1):
            postfix[i] = nums[i] * postfix[i + 1]
        
        answer = []
        for i in range(n):
            if i == 0:
                answer.append(postfix[i + 1])
            elif i == n - 1:
                answer.append(prefix[i - 1])
            else:
                answer.append(prefix[i - 1] * postfix[i + 1])
        return answer

Notes

Cards

START Basic Front: Product of Array Except Self Back: Use Prefix and Postfix, with prefix initialized into the result array and then gathering the postfix by ()()().

END

---

References

• Product of Array Except Self
• Product of array except self code bug | Claude