Skip to main content

24. Product of Array Except Self

mediumAsked at Square

Compute each payment terminal's contribution factor without dividing out that terminal's own volume — Square's analytics team uses a no-division prefix-product scan to generate per-merchant weight arrays for settlement-fee allocation without floating-point precision loss.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums fits in a 32-bit integer

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]

Approaches

1. Two pass with prefix and suffix arrays

Build a left-products array (prefix) and a right-products array (suffix). answer[i] = left[i] * right[i]. Clear and readable. O(n) time, O(n) space beyond output.

Time
O(n)
Space
O(n)
function productExceptSelf(nums) {
  const n = nums.length;
  const left  = new Array(n).fill(1);
  const right = new Array(n).fill(1);
  for (let i = 1; i < n; i++)     left[i]  = left[i - 1]  * nums[i - 1];
  for (let i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
  return left.map((l, i) => l * right[i]);
}

Tradeoff:

2. Constant space (accumulator pass)

First fill output with prefix products in one left pass. Then multiply in suffix products right-to-left using a running accumulator variable. Output array is the only extra space — O(1) extra beyond the required output.

Time
O(n)
Space
O(1)
function productExceptSelf(nums) {
  const n = nums.length;
  const ans = new Array(n).fill(1);
  // left pass: ans[i] = product of all nums[0..i-1]
  for (let i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1];
  // right pass: multiply in product of all nums[i+1..n-1]
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    ans[i] *= suffix;
    suffix *= nums[i];
  }
  return ans;
}

Tradeoff:

Square-specific tips

Square specifically grades the 'no division' constraint — handing them a solution using total product / nums[i] fails on zeros and violates the rules. Call out both failure modes immediately: 'division fails when nums[i]=0, and floating-point division loses precision on large products.' Then present the prefix-suffix approach. The O(1)-space variant is the bonus that signals senior-level thinking.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Product of Array Except Self and other Square interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →