LeetCode: 238 Product of Array Except Self

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:

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

Example:

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

问题

给定一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外的所有元素的乘积。

保证任何 nums 的前缀或后缀的乘积都在 32 位整数范围内。

你必须编写一个运行时间为 O(n) 且不使用除法操作的算法。

解决方案 1

前缀和后缀乘积方法

Approach 1 / 方法 1

This solution uses two passes to calculate the product of the array except for the current element. The idea is to first calculate the prefix product for each element and then the suffix product for each element, and finally, multiply the two to get the desired result.

该解决方案使用两次遍历来计算数组中除当前元素之外的乘积。其思想是首先计算每个元素的前缀乘积，然后计算每个元素的后缀乘积，最后将两者相乘得到所需结果。

Implementation / 实现

python

# Solution 1 implementation in Python
def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n

    # Calculate prefix product
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]

    # Calculate suffix product and multiply with prefix product
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]

    return answer

Explanation / 解释

1. Step 1 / 第一步:

• Initialize an array answer with all elements set to 1.
  初始化一个数组 answer，所有元素都设置为1。

2. Step 2 / 第二步:

• Calculate the prefix product for each element. For each element at index i, answer[i] contains the product of all elements to the left of i.
  计算每个元素的前缀乘积。对于索引 i 处的每个元素，answer[i] 包含 i 左边所有元素的乘积。

3. Step 3 / 第三步:

• Calculate the suffix product for each element and multiply it with the corresponding prefix product stored in answer.
  计算每个元素的后缀乘积，并将其与 answer 中存储的相应前缀乘积相乘。

4. Step 4 / 第四步:

• Return the final array answer.
  返回最终的数组 answer。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of elements in the array.
  时间复杂度: O(n)，其中n是数组中的元素数量。

• Space Complexity: O(1), considering the output array does not count as extra space.
  空间复杂度: O(1)，考虑到输出数组不算作额外空间。

解决方案 2

优化的前缀和后缀乘积方法

Approach 2 / 方法 2

This optimized approach involves two passes through the array but avoids the use of additional arrays by storing the results directly in the answer array. The idea remains the same: first, calculate the prefix products, and then calculate the suffix products while multiplying them directly into the answer array.

这种优化的方法涉及两次遍历数组，但通过直接在 answer 数组中存储结果，避免了使用额外的数组。其思想保持不变：首先计算前缀乘积，然后计算后缀乘积，并将它们直接乘入 answer 数组中。

Implementation / 实现

python

# Solution 2 implementation in Python
def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n

    # Calculate prefix product and store in answer
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]

    # Calculate suffix product and multiply in answer
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]

    return answer

Explanation / 解释

1. Step 1 / 第一步:

• Initialize the answer array with all elements set to 1. This array will eventually store the result.
  初始化 answer 数组，所有元素都设置为1。这个数组最终将存储结果。

2. Step 2 / 第二步:

• Iterate from left to right across the nums array, computing the prefix product for each element and storing it directly in the answer array.
  从左到右遍历 nums 数组，计算每个元素的前缀乘积，并将其直接存储在 answer 数组中。

3. Step 3 / 第三步:

• Iterate from right to left across the nums array, computing the suffix product for each element. Multiply this suffix product directly into the answer array.
  从右到左遍历 nums 数组，计算每个元素的后缀乘积。将这个后缀乘积直接乘入 answer 数组中。

4. Step 4 / 第四步:

• Return the final answer array, which now contains the product of all elements except the current one for each index.
  返回最终的 answer 数组，该数组现在包含除每个索引的当前元素之外的所有元素的乘积。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of elements in the array.
  时间复杂度: O(n)，其中n是数组中的元素数量。

• Space Complexity: O(1), since no extra space is used except for the output array.
  空间复杂度: O(1)，因为除了输出数组外，不使用额外的空间。

Summary / 总结

• Both approaches efficiently calculate the product of all elements in the array except for the current element without using division and with O(n) time complexity.
• The second approach is slightly more optimized as it directly uses the answer array for both prefix and suffix calculations, minimizing space usage.

Tips / 提示

• Consider how you can reuse the same array to store intermediate results and reduce space complexity.
• Ensure you understand how prefix and suffix arrays work to solve similar problems efficiently.

Solution Template for similar questions / 提示

• Use prefix and suffix products to efficiently calculate the product of arrays except for the current element.
• Implement in-place updates in the output array to reduce space complexity.

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of array manipulation, efficient memory usage, and the ability to implement algorithms that avoid division when required.

5 more similar questions / 推荐5问题

1. LeetCode 152. Maximum Product Subarray
2. LeetCode 53. Maximum Subarray
3. LeetCode 42. Trapping Rain Water
4. LeetCode 724. Find Pivot Index
5. LeetCode 135. Candy

More

Let’s break down the approach of dividing the product of an array by each element and discuss why this method, while seemingly straightforward, has significant pitfalls, particularly when the array contains zero. I’ll then explain an alternative solution using Python that addresses these challenges.

Initial Approach: Division Method

The idea here is simple:

1. Calculate the Product of All Elements: First, compute the product of all elements in the array.
2. Divide the Product by Each Element: To get the product of all elements except for the one at the current index, divide the total product by the element at that index.

This can be implemented as follows in Python:

def productExceptSelf(nums):
    n = len(nums)
    product = 1
    for num in nums:
        product *= num

    ans = []
    for num in nums:
        ans.append(product // num)

    return ans

The Problem with Zeros

While the above method works in theory, it fails when the array contains zeros. Division by zero is undefined in mathematics and will cause an error in most programming languages, including Python.

Issues:

1. Single Zero: If there is a single zero in the array, the division approach would fail at the position where the zero exists because dividing by zero is not allowed.
2. Multiple Zeros: If there are multiple zeros, the division method fails entirely because the product of the entire array would be zero, leading to zero in all positions of the result array, which is incorrect.

Enhanced Approach: Counting Zeros

To handle arrays containing zeros, we need a different approach:

1. Count the Number of Zeros:

   • If the count of zeros is greater than one, all elements in the result should be zero because multiplying any number by zero yields zero.
   • If there is exactly one zero, then all positions except the one corresponding to the zero in the original array should be zero. The position corresponding to the zero should be the product of all non-zero elements.
   • If there are no zeros, we can revert to the division-based approach but without actually performing the division.

2. Compute the Product for Non-Zero Elements:

   • Compute the product of all non-zero elements and then apply the logic based on the count of zeros.

Here is the implementation in Python:

def productExceptSelf(nums):
    n = len(nums)
    zero_count = nums.count(0)

    # If more than one zero, all elements in the result should be zero
    if zero_count > 1:
        return [0] * n

    # Calculate the product of all non-zero elements
    product = 1
    for num in nums:
        if num != 0:
            product *= num

    ans = []
    for num in nums:
        if zero_count == 0:
            ans.append(product // num)
        elif zero_count == 1:
            # If current element is zero, place the product, otherwise place zero
            ans.append(product if num == 0 else 0)

    return ans

Explanation

• Step 1: Count Zeros: We count the number of zeros in the array using nums.count(0). Depending on the number of zeros, we have three different cases to handle.

• Step 2: Handle Special Cases:

  • Multiple Zeros: If more than one zero exists, the entire result array should be zeros.
  • Single Zero: If exactly one zero exists, the only non-zero element in the result should be at the position of that zero in the original array, and it should be the product of all non-zero elements.
  • No Zeros: If there are no zeros, we calculate the product except for each element normally.

• Step 3: Calculate the Product: We calculate the product of all non-zero elements and then construct the result based on the above conditions.

Time Complexity

This enhanced approach also runs in O(n) time, which is efficient given the constraints of the problem. It handles edge cases with zeros gracefully and avoids the pitfalls of division by zero.

Conclusion

The division approach seems intuitive but breaks down in the presence of zeros, which is a common edge case in real-world data. The enhanced approach using multiplication and careful handling of zeros is robust, efficient, and ensures correctness across all possible inputs. Understanding and addressing such edge cases can help you stand out in an interview by demonstrating not only problem-solving skills but also the ability to anticipate and resolve potential issues in your solutions.

Recommended Resources:

LeetCode #238: Product of Array Except Self | Prefix Sum by Algo Engine