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

Thinking Process

  1. Two Arrays Approach: Use separate arrays for left and right products for clarity
  • Two indices move toward each other or in the same direction.
  • Works on sorted arrays or when in-place modification is required.
  • Loop invariant: all indices outside [left, right] are already resolved.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Opposite ends (this problem) O(n) O(1) Sorted array pair search, reversal
Slow / fast pointers O(n) O(1) Linked list middle, cycle detection
Same-direction chase O(n) O(1) Remove duplicates in-place
Sliding window (variable) O(n) O(1) Subarray with constraint

Examples

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

Space-Optimized Solution

We can optimize space by using the output array itself to store left products, then building right products on the fly:

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        
        L = [0] * n
        R = [0] * n
        answer = [0] * n
        
        L[0] = 1
        for i in range(1, n):
            L[i] = nums[i - 1] * L[i - 1]
        
        R[n - 1] = 1
        for i in range(n - 2, -1, -1):
            R[i] = nums[i + 1] * R[i + 1]
        
        for i in range(n):
            answer[i] = L[i] * R[i]
        
        return answer

Space Complexity: O(1) extra space (excluding output array)

Common Mistakes

  1. Two elements: nums = [2, 3] → answer = [3, 2]
  2. Contains zero: nums = [-1,1,0,-3,3] → answer = [0,0,9,0,0]
  3. All same: nums = [2,2,2] → answer = [4,4,4]
  4. Negative numbers: nums = [-1,2,-3,4] → answer = [24,-12,8,-6]

  5. Single zero: nums = [1,0,3,4] → answer = [0,12,0,0]

  6. Using division: answer[i] = totalProduct / nums[i] fails with zeros
  7. Wrong initialization: Forgetting to set L[0] = 1 and R[len-1] = 1
  8. Index off-by-one: Confusing left/right boundaries
  9. Integer overflow: Not considering product might exceed 32-bit (but constraints guarantee it won’t)
  10. Space optimization: Not realizing we can use output array for left products

Comparison with Alternative Approaches

Approach Time Space Notes
Left/Right Arrays O(n) O(n) Clear and intuitive
Space-Optimized O(n) O(1) Uses output array
Division (Invalid) O(n) O(1) Fails with zeros

Key Takeaways

  1. Two Arrays Approach: Use separate arrays for left and right products for clarity

  2. Space Optimization: Can use output array to store left products, then build right products on the fly

  3. No Division: Avoids division operator, which would fail with zeros

  4. Handles Zeros: Works correctly even when array contains zeros

  5. Prefix/Suffix Products: Similar to prefix sum, but with multiplication

References

Template Reference