Skip to main content

238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

Python​

Force Busted (Timelimit Exceed)​

  • Time: O(N^2)
  • Space: O(1)
from functools import reduce


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        return [
            reduce(lambda cur, num: cur*num, nums[:i]+nums[i+1:], 1)
            for i in range(len(nums))
        ]

Cache the Left and Right​

  • Time: O(N)
  • Space: O(2N)
from collections import deque


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

        lefts = [1]
        rights = deque([1])

        for i in range(1, length):
            # i from 1~n
            lefts.append(lefts[i-1] * nums[i-1])

        for i in range(length-1):
            # length-1-i: 1~n
            rights.appendleft(rights[0] * nums[length-1-i])

        return [lefts[i]*rights[i] for i in range(length)]