Leetcode 238 - Product of Array Except Self

Difficulty: medium

Table of contents

Open Table of contents

Problem

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:

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

Explanation/Approach

This problem requires calculating the product of all elements in the array except the current one, without using division. A key insight is to use prefix and suffix products.

Solution 1: Prefix and Suffix Product Arrays

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

        # Arrays to hold the prefix and suffix products
        left_products = [1] * length
        right_products = [1] * length
        answer = [0] * length

        # Calculate left products
        for i in range(1, length):
            left_products[i] = nums[i - 1] * left_products[i - 1]

        # Calculate right products
        for i in reversed(range(length - 1)):
            right_products[i] = nums[i + 1] * right_products[i + 1]

        # Calculate the answer array
        for i in range(length):
            answer[i] = left_products[i] * right_products[i]

        return answer

Time and Memory Complexity

The time complexity is O(n) as it requires traversing the array three times. The space complexity is O(n) for the two additional arrays.

Explanation

We use two extra arrays to store the left and right products for each index. The final answer for each index is then the product of its corresponding left and right values.



Solution 2: Space Optimized Approach

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

        # Calculate left products and store them in answer
        answer[0] = 1
        for i in range(1, length):
            answer[i] = nums[i - 1] * answer[i - 1]

        # Calculate right products and accumulate in answer
        right_product = 1
        for i in reversed(range(length)):
            answer[i] = answer[i] * right_product
            right_product *= nums[i]

        return answer

Time and Memory Complexity

The time complexity remains O(n) for traversing the array twice. The space complexity is improved to O(1), as it only uses the answer array and a single variable for the right products.

Explanation

This solution first calculates the left products directly into the answer array. Then, it traverses the array from the end, multiplying each element in the answer array by the running product of elements to the right. This method effectively combines the two steps of the previous solution, thereby saving space.

Visualization:

Imagine the input array nums is [2, 3, 4, 5]. The process would look like this:

  1. Initial State:

    nums:   [2, 3, 4, 5]
answer: [0, 0, 0, 0]

  2. After Calculating Left Products:

    nums:   [2, 3, 4, 5]
answer: [1, 2, 6, 24]  # [1, 2, 2*3, 2*3*4]

  3. Calculating Right Products:

    • Iteration starts from the end.
    • Update the answer array by multiplying each element by right_product and update right_product.
    # First iteration (i = 3)
right_product = 1
answer: [1, 2, 6, 24] -> [1, 2, 6, 24*1]

# Second iteration (i = 2)
right_product = 5
answer: [1, 2, 6, 24] -> [1, 2, 6*5, 24]

# Third iteration (i = 1)
right_product = 20 (5*4)
answer: [1, 2, 30, 24] -> [1, 2*20, 30, 24]

# Fourth iteration (i = 0)
right_product = 60 (20*3)
answer: [1, 40, 30, 24] -> [1*60, 40, 30, 24]

  4. Final Result:

    nums:   [2, 3, 4, 5]
answer: [60, 40, 30, 24]