Hex.*

LC238 - Product of Array Except Self

Posted on In
Leetcode: 115/2658 (51+51+13)

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 <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

  1. Traverse nums once from left to right, and store the product of the current number in the remaining product result
  2. Traverse nums once from right to left, and store the product of the right side of the current number in the result of the correct product
  3. Multiply the results of the left product and the right product, which is the product of the numbers other than yourself

optimization:

In the last traversal from left to right, store the result directly in the loop of numbers from right to right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# O(n) time | O(n) space
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        leftproduct = [1 for _ in range(len(nums))]
        rightproduct = [1 for _ in range(len(nums))]

        for i in range(1, len(nums)):
            leftproduct[i] = leftproduct[i-1] * nums[i-1]

        for i in reversed(range(len(nums)-1)):
            rightproduct[i] = rightproduct[i+1] * nums[i+1]

        for i in range(len(nums)):
            leftproduct[i] *= rightproduct[i]
        return leftproduct

# O(n) time | O(1) space
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1 for _ in range(len(nums))]

        for i in range(1, len(nums)):
            res[i] = res[i-1] * nums[i-1]

        temp = 1
        for i in reversed(range(len(nums))):
            res[i] = temp * res[i]
            temp *= nums[i]
        return res