29. 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]. You must write an algorithm that runs in O(n) time and without using the division operation.

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

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

Problem Breakdown:

1. The answer for each index is the product of all elements to its left multiplied by the product of all elements to its right. We compute these in two passes.

• n = len(nums)
  result = [1] * n

2. First pass (left to right): compute the prefix product for each position. result[i] holds the product of all elements before index i.

• prefix = 1
  for i in range(n):
      result[i] = prefix
      prefix *= nums[i]

3. Second pass (right to left): multiply each result[i] by the suffix product (product of all elements after index i).

• suffix = 1
  for i in range(n - 1, -1, -1):
      result[i] *= suffix
      suffix *= nums[i]

4. After both passes, result[i] = prefix_product * suffix_product = product of all elements except self.

• return result

Summary:

Two-pass approach without division. First pass computes prefix products (product of all elements before each index). Second pass multiplies by suffix products (product of all elements after each index). The result at each index is the product of everything except itself.

Time and Space Complexity:

Time Complexity: O(n) - two passes through the array.

Space Complexity: O(1) - the output array does not count as extra space per the problem statement.

Python Solution:

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

JavaScript Solution:

var productExceptSelf = function(nums) {
    const n = nums.length;
    const result = new Array(n).fill(1);
    let prefix = 1;
    for (let i = 0; i < n; i++) {
        result[i] = prefix;
        prefix *= nums[i];
    }
    let suffix = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= suffix;
        suffix *= nums[i];
    }
    return result;
};

Java Solution:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int prefix = 1;
        for (int i = 0; i < n; i++) {
            result[i] = prefix;
            prefix *= nums[i];
        }
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }
        return result;
    }
}