Skip to content

238. Product of Array Except Self

Medium

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.

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 <= 10⁡.
  • -30 <= nums[i] <= 30
  • The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

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.)

Solutions πŸ”’

Video Solution Coming Soon

Approach: PrefixSum

Algorithm Template

Build a prefix sum

def fn(arr):
    prefix = [arr[0]]
    for i in range(1, len(arr)):
        prefix.append(prefix[-1] + arr[i])

    return prefix

Way 1: Using Two arrays

Time complexity: \(O(n)\)

Space complexity: \(O(n)\)

where \(n\) is the no. of elements in the input array

Algorithm

To solve this problem efficiently without using division, we’ll use two additional arrays.

First, we'll create a left product array β€œfrom_left” where each element at index i represents the product of all elements to the left of nums[i].

Then, we'll create a right product array β€œfrom_right” where each element at index i represents the product of all elements to the right of nums[i].

Finally, we'll compute the result array β€œres” by multiplying corresponding elements from β€œfrom_left” and β€œfrom_right”.

Time complexity of this solution is O(n).

class Solution: # 2 extra arrays
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)

        #Initialize left product array
        from_left = [1]*n
        # Product from index=0 to index=i-1
        for i  in range(1,n):
            from_left[i] = from_left[i-1]*nums[i-1]

        #Initialize right product array
        from_right = [1]*n
        # Product from index=n-1 to current position
        for i  in range(n-2,-1,-1):
            from_right[i] =from_right[i+1]*nums[i+1]

        #Compute answer
        res = [1]*n
        for i in range(n):
            res[i] = from_left[i]*from_right[i]

        return res
quick tip

Use List comprehension it is efficient

res = [from_left[i]*from_right[i] for i in range(n)]

        V
      better
        V

res = [1]*n
for i in range(n):
    res[i] = from_left[i]*from_right[i]

Way 2: Optimized Approach for Follow Up

Time complexity: \(O(n)\)

Space complexity: \(O(1)\)

Algorithm

We define two variables left and right, which represent the product of all elements to the left and right of the current element respectively.

Initially, left = 1, right = 1. Define an answer array ans of length n.

We first traverse the array from left to right, for the ith element we update ans[i] with left, then left multiplied by nums[i].

Then, we traverse the array from right to left, for the ith element, we update ans[i] to ans[i]*right, then right multiplied by nums[i].

After the traversal, the array ans is the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).

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

    ans = [1]*n

    #traverse the array from left to right
    left =1
    for i in range(n):
        ans[i]=left
        left = left*nums[i]

    #traverse the array from right to left
    right = 1
    for i in range(n-1, -1, -1):
        ans[i] = ans[i]*right
        right = right*nums[i]

    return ans
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments