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]. You must solve this problem without using any division operation and in O(n) time complexity.

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.

Example:

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

Solution

Problem Analysis:

  • We need to compute the product of all numbers except the number at the current index.
  • Crucially, we cannot use the division operator.
  • The solution must have O(n) time complexity.

Approach: Prefix and Suffix Products (Optimized Space) The core idea is that for any index i, the product of all elements except nums[i] can be found by multiplying the product of elements to its left (prefix product) by the product of elements to its right (suffix product).

To achieve O(1) space complexity (excluding the output array), we can use two passes:

  1. First Pass (Left-to-Right - Calculate Prefix Products):

    • Initialize an answer array of the same size as nums, filled with 1s.
    • Initialize a prefix_product variable to 1.
    • Iterate through nums from left to right (from index 0 to n-1):
      • At each index i, set answer[i] to the current prefix_product (which represents the product of all elements before nums[i]).
      • Update prefix_product by multiplying it with nums[i]. After this step, prefix_product will store the product of nums[0]...nums[i].
    • After this pass, answer[i] contains the product of all elements to the left of i.

  2. Second Pass (Right-to-Left - Incorporate Suffix Products):

    • Initialize a suffix_product variable to 1.
    • Iterate through nums from right to left (from index n-1 down to 0):
      • At each index i, multiply the current value in answer[i] (which holds the prefix product) by suffix_product (which represents the product of all elements after nums[i]). This completes the answer[i] calculation.
      • Update suffix_product by multiplying it with nums[i]. After this step, suffix_product will store the product of nums[i]...nums[n-1].

Complexity Analysis:

  • Time Complexity: O(n) because we perform two passes over the input array, each taking linear time.
  • Space Complexity: O(1) (excluding the output array answer which is required for the result).
class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        
        # Initialize the answer array with 1s. 
        # This array will store the final result.
        answer = [1] * n
        
        # First pass: Calculate prefix products
        # answer[i] will store the product of all elements to the left of index i.
        # For index 0, there are no elements to the left, so answer[0] remains 1 initially.
        prefix_product = 1
        for i in range(n):
            answer[i] = prefix_product
            prefix_product *= nums[i]
            
        # Second pass: Calculate suffix products and combine with prefix products
        # suffix_product will store the product of all elements to the right of index i.
        # For the last index (n-1), there are no elements to the right, 
        # so suffix_product starts as 1.
        suffix_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix_product
            suffix_product *= nums[i]
            
        return answer