238. Product of Array Except Self

Q: Why is the empty product 1?

By convention, a product over an empty set of factors is 1, the multiplicative identity. prefix[0] = 1 means 'no elements to the left of index 0'.

Q: Why doesn't the output array count toward the O(1) space claim?

The problem requires an output array of size n; storing it is unavoidable. Extra space refers to auxiliary structures beyond the required output.

Q: What happens if all elements are zero?

prefix and suffix are all zero after index 0/before index n-1; answer[i] = 0 for every i. Correct — no product is defined as nonzero.

mediumAsked at Anduril

Compute for each index the product of all other elements without using division. Anduril asks this to verify you can maintain running prefix and suffix state in a single-pass — a technique that appears in sensor-normalization pipelines where you need context from both sides of a measurement without reprocessing the full array.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Anduril loops.

Glassdoor (2025-12)— Mentioned in Anduril SWE onsite reports as a prefix/suffix state medium question.
Blind (2025-10)— Anduril engineer threads cite this problem as a reliable signal of whether candidates can think in prefix/suffix passes.

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 is guaranteed to fit in a 32-bit integer.

Examples

Example 1

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.

Example 2

Input

nums = [-1,1,0,-3,3]

Output

[0,0,9,0,0]

Explanation: The zero makes every product except at index 2 equal to 0.

Approaches

1. Prefix and suffix arrays

Build prefix[i] = product of nums[0..i-1] and suffix[i] = product of nums[i+1..n-1]. answer[i] = prefix[i] * suffix[i].

Time: O(n)
Space: O(n)

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

Tradeoff: Clearly shows the two-pass structure. Uses O(n) extra space for prefix and suffix arrays.

2. Space-optimized (output array + running suffix)

Use the output array itself as the prefix. Then do a right-to-left pass with a running suffix variable, multiplying into the output in-place.

Time: O(n)
Space: O(1) extra (not counting the output array)

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  // Left pass: answer[i] holds the product of all elements to the left of i
  for (let i = 1; i < n; i++) answer[i] = answer[i - 1] * nums[i - 1];
  // Right pass: multiply in the product of all elements to the right
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }
  return answer;
}

Tradeoff: O(1) extra space (the output array is not counted). This is the preferred answer at Anduril — it shows you can collapse two auxiliary arrays into one output + one scalar.

Anduril-specific tips

State the core insight before coding: 'answer[i] = (product of everything left of i) * (product of everything right of i). I can build both in O(n) using prefix and suffix passes.' Anduril engineers will follow up with the O(1) space optimization — proactively offer it. Also mention the zero-handling edge case: if nums contains two or more zeros, all answers are zero; if exactly one zero, only the position of the zero has a nonzero product.

Common mistakes

Using division — explicitly forbidden by the problem.
Forgetting to initialize prefix[0] = 1 and suffix[n-1] = 1 (the empty product is 1).
In the space-optimized version, updating suffix *= nums[i] before multiplying answer[i] *= suffix — must multiply first, then advance the suffix.
Not handling zeros — zeros propagate through the products and the standard algorithm handles them correctly, but many candidates assume zero is a special case requiring extra code.

Follow-up questions

An interviewer at Anduril may pivot to one of these next:

How would you extend this to a 2D matrix — product of all elements except those in the same row and column?
What if the array can contain very large numbers and you need to work modulo 10^9+7?
Can you parallelize the two passes on a multi-core processor? What is the dependency structure?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the empty product 1?

By convention, a product over an empty set of factors is 1, the multiplicative identity. prefix[0] = 1 means 'no elements to the left of index 0'.

Why doesn't the output array count toward the O(1) space claim?

The problem requires an output array of size n; storing it is unavoidable. Extra space refers to auxiliary structures beyond the required output.

What happens if all elements are zero?

prefix and suffix are all zero after index 0/before index n-1; answer[i] = 0 for every i. Correct — no product is defined as nonzero.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →