#238

Medium

LeetCode Problem Workspace

Product of Array Except Self

Solve the 'Product of Array Except Self' problem by calculating the product of all elements except self for each index efficiently.

array prefix sum

Problem Statement

Given an integer array nums, you need to return an array answer such that answer[i] is equal to the product of all elements in nums except nums[i]. The challenge lies in calculating this product without directly using division, as the problem requires a solution that operates in O(n) time.

The product of any prefix or suffix of nums will fit within the 32-bit integer limit. This means that while calculating the products, the result for each index must be the product of all elements excluding the current one, using an efficient method to avoid division operations.

Examples

Example 1

Input: nums = [1,2,3,4]

Output: [24,12,8,6]

Example details omitted.

Example 2

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

Output: [0,0,9,0,0]

Example details omitted.

Constraints

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Solution Approach

Prefix and Suffix Product Arrays

By constructing two auxiliary arrays (prefix and suffix products), you can calculate the desired product for each index. The prefix product stores the product of all elements before the current index, and the suffix product stores the product of all elements after it. The final answer for each index is the product of the corresponding values in these arrays.

In-place Calculation with Two Passes

Instead of using additional space for prefix and suffix arrays, you can optimize the space complexity by performing two passes over the input array. In the first pass, fill the result array with the prefix product values. Then, in the second pass, multiply each element by the suffix product as you traverse from right to left.

Time and Space Optimization

To achieve both time and space efficiency, the algorithm must run in O(n) time and require only O(1) extra space (excluding the output array). This can be achieved by using the result array to store the intermediate products during the two-pass process.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because we traverse the array twice: once from left to right for the prefix product and once from right to left for the suffix product. The space complexity is O(1) if we disregard the output array, as we use the result array to store intermediate calculations, eliminating the need for additional storage.

What Interviewers Usually Probe

Candidate's ability to efficiently use prefix and suffix products to avoid unnecessary calculations.
Understanding of optimizing space complexity, especially avoiding extra arrays for prefix and suffix products.
Clarity in explaining how to achieve the desired result in O(n) time without using division.

Common Pitfalls or Variants

Common pitfalls

Incorrectly using division to calculate the product, which violates the problem's constraints.
Failing to consider edge cases like zeros in the input array, which may lead to incorrect results if not handled properly.
Not understanding the importance of optimizing space usage by avoiding unnecessary auxiliary arrays.

Follow-up variants

Handling larger input arrays, where O(n) time complexity and O(1) space complexity are crucial.
Considering cases with multiple zeros in the array, which will require special handling to avoid incorrect products.
Implementing a solution that doesn't require additional memory for prefix and suffix arrays but still ensures efficiency.

FAQ

What is the main algorithmic approach for solving 'Product of Array Except Self'?

The key approach is using prefix and suffix products. Calculate the product of all elements before and after each index and combine them to get the result.

How can I solve the problem without using division?

By using two auxiliary arrays or performing two passes over the input array, you can compute the result without division by storing intermediate products.

Can the 'Product of Array Except Self' problem be solved in O(n) time?

Yes, by utilizing prefix and suffix products, you can solve the problem in O(n) time with two passes through the array.

What is the space complexity of the optimal solution for this problem?

The optimal solution has O(1) space complexity, excluding the output array, by reusing the result array for intermediate calculations.

How do you handle zeros in the input array for this problem?

Zeros must be carefully handled, as they will make the product of all elements except the current one equal to zero. The solution needs to account for multiple zeros in the array.

terminal

Solution

Solution 1: Two Passes

We define two variables $\textit{left}$ and $\textit{right}$ to represent the product of all elements to the left and right of the current element, respectively. Initially, $\textit{left} = 1$ and $\textit{right} = 1$. We define an answer array $\textit{ans}$ of length $n$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        left = right = 1
        for i, x in enumerate(nums):
            ans[i] = left
            left *= x
        for i in range(n - 1, -1, -1):
            ans[i] *= right
            right *= nums[i]
        return ans

Continue Practicing

#209 minimum size subarray sum #303 range sum query immutable #304 range sum query 2d immutable