Problem Statement

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.

Examples

Example 1:

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

Example 2:

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

Constraints

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Key Insights

We can solve this problem in two passes to achieve an O(N) runtime. In the first forward pass, we calculate the left prefix multiple and store it an out list. (We store the product of the elements before index i at each index i). In the second reverse pass, we maintain a right variable that keeps track of the right suffix multiple. As we iterate backwards through the out list we update the value at index i with the product of the left prefix multiple (stored at index i) and the right suffix multiple (the right variable).

Python Solution

Brute Force (TLE)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        """
            T: O(N^2)
            S: O(N)
        """
        n = len(nums)
        out = [1] * n

        # Note: This approach will
        #       experience a time
        #       limit exception (TLE)
        #       on Leetcode.
        #
        # The outer for loop iterates 
        # from 0 to n - 1.
        # The inner for loop iterates
        # from i + 1 to n - 1.
        # The "left" variable keeps
        # track of the product of all
        # elements before i, and 
        # "right" keep track of the
        # product all elements to the
        # right of i.

        left = 1
        # Iterate through nums
        for i in range(n):
            
            # calculate right product
            right = 1
            for j in range(i + 1, n):
                right *= nums[j]

            # Calculate product excluding self
            out[i] = right * left

            # Calculate left product
            left *= nums[i]

        return out

Optimized

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        """
            T: O(N)
            S: O(N)

            nums = [1,  2,  3,  4]

            # first pass
            out  = [1,  1,  2,  6]
                                ^

            # second pass
            right = 24
            out  = [24, 12, 8,  6]
                    ^
            
        """
        n = len(nums)
        out = [1] * n

        # Calculate the product of all
        # elements to the left of i and
        # save the results in the out
        # list.
        left = 1
        for i in range(n):
            out[i] = left
            left *= nums[i]

        # Loop backwards from the end and
        # calculate the product of all 
        # elements to the right of i
        # and multiply it by the product
        # of all elements to the left
        # (already stored at i).
        right = 1
        for i in range(n-1, -1, -1):
            out[i] *= right
            right *= nums[i]

        return out