Product of Array Except Self

238. Product of Array Except Self

Medium

Return an array where each element is the product of all elements except itself.

ArrayPrefix Sum

View Problem

Problem Statement

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 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 input is generated such that answer[i] is guaranteed to fit in a 32-bit integer

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Try It Yourself

TypeScript

function productExceptSelf(nums: number[]): number[] {
    // Your solution here
}

Go

func productExceptSelf(nums []int) []int {
    // Your solution here
}

Solution

Click to reveal solution

Use left and right products calculated in a single pass to achieve O(1) extra space.

TypeScript Solution

function productExceptSelf(nums: number[]): number[] {
  let left = 1;
  let right = 1;

  const res = new Array(nums.length).fill(1);

  for (let l = 0; l < nums.length; l++) {
      const r = nums.length - l - 1;

      res[l] *= left;
      res[r] *= right;

      left *= nums[l];
      right *= nums[r];
  }

  return res;
}

Time:O(n)

Space:O(1)

Go Solution

func productExceptSelf(nums []int) []int {
  left := 1
  right := 1
  n := len(nums)
  
  res := make([]int, n)
  for i := range res {
      res[i] = 1
  }

  for l := 0; l < n; l++ {
      r := n - l - 1

      res[l] *= left
      res[r] *= right

      left *= nums[l]
      right *= nums[r]
  }

  return res
}

Time:O(n)

Space:O(1)

Algorithm:

1. Initialize result array with all 1s
2. Use two pointers: left (from start) and right (from end)
3. In each iteration:
   • Multiply result[left] by the current left product
   • Multiply result[right] by the current right product
   • Update left and right products for next iteration
4. This simultaneously builds left products and right products in one pass

Time Complexity: O(n) - single pass through the array Space Complexity: O(1) - only using constant extra space (not counting output array)

Traditional Two-Pass Approach:

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n);
    
    // First pass: calculate left products
    result[0] = 1;
    for (let i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }
    
    // Second pass: multiply by right products
    let rightProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}

Key Insight: For each position i, the result is the product of all elements to the left of i multiplied by the product of all elements to the right of i.