LeetCode 238: Product of Array Except Self

Problem Description

Difficulty: Medium

Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].

Each product is guaranteed to fit in a 32-bit integer.

LeetCode version: You must write an algorithm that runs in \(O(n)\) time and without using the division operation.

NeetCode version: Follow-up: Could you solve it in \(O(n)\) time without using the division operation?

Example 1:

Input: nums = [1,2,4,6]
Output: [48,24,12,8]

Example 2:

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

Constraints:

 2 <= nums.length <= 1000
-20 <= nums[i] <= 20

Initial Solution

This is known as “Products of Array Discluding Self” on NeetCode. The problem there allows you to use the division operation, so I went with the easy route first.

from typing import List

class InitialSolution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        product = 1
        contains_zero = False
        zeros = []

        for i, n in enumerate(nums):
            if n == 0:
                contains_zero = True
                zeros.append(i)
            else:
                product *= n

        if not contains_zero:
            return [product // n for n in nums]

        # If more than one zero, all products will be zero:
        if len(zeros) > 1:
            return [0] * len(nums)

        # If exactly one zero
        return [0 if i not in zeros else product for i, _ in enumerate(nums)]

nums_tests = [
    ([1, 2, 4, 6], [48, 24, 12, 8]),
    ([-1, 0, 1, 2, 3], [0, -6, 0, 0, 0]),
    ([0, 0], [0, 0])
]

solution = InitialSolution()

for nums, expected_output in nums_tests:
    result = solution.productExceptSelf(nums)
    print(f"Input: {nums}\nExpected: {expected_output}\nOutput: {result}\n")

Input: [1, 2, 4, 6]
Expected: [48, 24, 12, 8]
Output: [48, 24, 12, 8]

Input: [-1, 0, 1, 2, 3]
Expected: [0, -6, 0, 0, 0]
Output: [0, -6, 0, 0, 0]

Input: [0, 0]
Expected: [0, 0]
Output: [0, 0]

Well, my code became a little convoluted trying to deal with the edge cases involving zeros. I tried it on LeetCode, not realizing that division was not allowed. Somehow it was accepted and beat 81% of submissions for time and 92% for memory.

No doubt there is a better way to deal with the zeros; maybe just count them up as we go, rather than flag their presence. That way we could break out of the loop early to return [0] * len(nums) as soon as we see two zeros.

• Time complexity: \(O(n)\) for the intial loop + \(O(n)\) for the results = \(O(n)\) overall
• Space complexity: \(O(n)\) for the results list and potentially for the zeros list too if nums is all 0.

LeetCode analyzed this as using \(O(1)\) space, but considers that “The output array does not count as extra space for space complexity analysis”.

After reading youtube comments on this problem, I learned that LeetCode will apparently reject a solution that contains the division operator. My solution used integer division // which somehow escaped this rule. Others complained that Leetcode would also reject multiple subtraction operations, so I really don’t understand what’s going on. I guess they relaxed the requirements recently. Relatedly, some bright spark on youtube suggested using math.pow(num,-1) to hack the requirements 😄

NeetCode Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * (len(nums))

        for i in range(1, len(nums)):
            res[i] = res[i-1] * nums[i-1]
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]
        return res

Conclusion

NeetCode’s solution computes the product of all elements in the array except the current element using a two-pass approach. It uses prefix and postfix multiplication techniques to achieve this in linear time without using division.