Leetcode Problem 238: Product of Array Except Self

Problem description:

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.

Since we cannot use the division operator, and the solution has to run in $ O(n) $ time, I figured that I will have to, to some capacity, use prefix/suffix arrays to solve this. But laziness is king, so I tried to brute force my way first hoping for the best,

1st attempted Python solution Link to heading


# leetcode_238.py


class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        res = []

        for i in range(0, n):
            sentinel = nums[i]  # the element to be ignored in the product
            product = 1
            for j in range(0, n):
                current = nums[j]
                if j == i:
                    continue
                product *= current

            res.insert(i, product)

        return res

and was greeted with:

Time Limit Exceeded

So had to go back to thinking about prefix/suffix arrays. Following is the second attempt

2nd attempted Python solution Link to heading


# leetcode_238.py


class Solution:
     def productExceptSelf(self, nums: list[int]) -> list[int]:
         n = len(nums)
         result = []

         for i in range(0, n):
             # the final 1 is an initialiser for when the list is empty;
             # also chose 1 because it's the neutral element in multiplication
             prefix_products = reduce(lambda x, y: x * y, nums[: i], 1)
             suffix_products = reduce(lambda x, y: x * y, nums[i + 1:], 1)
             total = prefix_products * suffix_products
             result.insert(i, total)

         return result

and was greeted again with:

Time Limit Exceeded

Yet I couldn’t discard the prefix/suffix intuition has I felt it was the key to solving this. So I figured that I needed to precompute the prefix and suffix arrays, both of which require $ O(n) $ time, but this time are not nested so overall it’s still $ O(n)$, instead of $ O(n^2) $ from previous attempts. After the arrays have been created, we can iterate through the input array while also keeping track of the current index in the input and prefix array, and the next index in the suffix array.

Python solution Link to heading


# leetcode_238.py


class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = []
        prefix_products = [1] * (n + 1)
        for k in range(1, n + 1):
            prefix_products[k] = prefix_products[k - 1] * nums[k - 1]

        reversed_nums = list(reversed(nums))
        suffix_products = [1] * (n + 1)
        for k in range(1, n + 1):
            suffix_products[k] = suffix_products[k - 1] * reversed_nums[k - 1]
        suffix_products = list(reversed(suffix_products))
        # the solution requires us to iterate one more time through the initial array,
        # but this time keeping track of the values of the current index, the previous 
        # index in the prefix array and the next one in the suffix array.
        #
        # Note how there's no out of bounds/range error because the prefix and suffix arrays have
        # one extra element (the initial default 1)
        for i in range(0, n):
            prod = prefix_products[i] * suffix_products[i + 1]
            result.insert(i, prod)

        return result

I was happy to have solved this, but it turns out that the code above would fail the follow up question:

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

So the hint here is that there’s a way to compute the prefixes and suffixes without actually storing the values in their own array but in the output array directly, since that is not counted in space complexity.

Python statistics Link to heading
Runtime: 281 ms - beats  59.26 % of python3 submissions.
Memory Usage: 22.1 MB -- 29.76 % of python3 submissions.
Complexity analysis Link to heading

  • Time: $ O(n + n + n) = O(3n) = 3 ~O(n)$, where every $ n $ coincides with the for loops iteration.

  • Space: $ O(n + m) = O(n + n) = 2 ~ O(n) = O(n) $ since we create two arrays for the prefixes and suffixes.



Share on:
LinkedIn