Leetcode: 238. Product of Array Except Self

• Pattern: Find cumulative product of an array

• Can we break-down the problem in small and easily to solve parts?
• Can we solve the problem by iterating from left to right (or right to left)?

The problem is specific about the time and space complexity. It expects a solution with time complexity of \(O(n)\) and space complexity of \(O(1)\). This is already a big hint for us, since we know that it is possible to solve the problem without using extra memory. Is there an alternative problem easier to solve? Yes, there is: return \(answer\) where \(answer[i]=nums[0] \times nums[1] \times ... \times nums[i-1]\). With a simple iteration, we can compute this \(answer\) without using extra memory. If the problem were to find \(answer\) where \(answer[i]=nums[n-1] \times nums[n-2] \times ... \times nums[i+1]\), it can also be solved with a simple iteration. Is it possible to combine these two problem and solve the original one? Yes, but I will leave it for you to do.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        cur = 1
        ans = []
        for n in nums:
            ans.append(cur)
            cur = cur * n
        cur = 1
        for i in range(len(nums) - 1, -1, -1):
            ans[i] = ans[i] * cur
            cur = cur * nums[i]
        return ans

• Interview preparation: V