Skip to main content

238. Product of Array Except Self

mediumAsked at AMD

Return an array where each element is the product of all other elements, without using division and in O(n). AMD uses this to test prefix/suffix scan thinking — the same left-pass/right-pass pattern underlies SIMD prefix-sum instructions, parallel reduction, and scan primitives on GPU hardware.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates report Product of Array Except Self as a medium problem emphasizing prefix/suffix scan in onsite rounds.
  • Blind (2025-11)— AMD interview threads highlight this as a problem that rewards candidates who know parallel scan primitives.

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 causes most products to be 0.

Approaches

1. Left-pass + Right-pass (O(n) space)

Compute prefix products into a left array and suffix products into a right array. answer[i] = left[i] * right[i].

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: O(n) time, O(n) space. Clear and explicit — good for explaining the approach before optimizing.

2. Space-optimized (O(1) extra space)

Use the output array for the left prefix products. Then scan right to left, accumulating the right product in a single variable and multiplying into the output array.

Time
O(n)
Space
O(1) extra (output array not counted)
function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  // Left pass: answer[i] = product of all elements to the left
  for (let i = 1; i < n; i++) answer[i] = answer[i - 1] * nums[i - 1];
  // Right pass: multiply by running right product
  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= rightProduct;
    rightProduct *= nums[i];
  }
  return answer;
}

Tradeoff: O(1) extra space — the output array doesn't count. The right product is folded into a single running variable. This is the expected answer in AMD interviews.

AMD-specific tips

The prefix/suffix scan pattern is fundamental to GPU parallel computing. AMD's ROCm/HIP exposes hardware prefix-sum (inclusive/exclusive scan) primitives that operate in O(log n) parallel steps. Frame your answer in terms of two passes — one left, one right — and note that on a multi-core CPU or GPU this generalizes to parallel scan: 'these two passes can be run in parallel across segments, which is exactly how GPU scan primitives work.' This shows architectural awareness AMD values highly.

Common mistakes

  • Using division — explicitly prohibited and fails on zeros.
  • Not initializing rightProduct to 1 before the right pass.
  • Off-by-one: left[i] should be the product of nums[0..i-1] (exclusive of i), so start the loop at i=1 with left[0]=1.
  • Forgetting to update rightProduct after multiplying into answer[i].

Follow-up questions

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

  • What if the array contains zeros — does the solution still work? (Yes — zeros propagate naturally.)
  • How does this generalize to a prefix sum on GPU with warp-level primitives?
  • Maximum Product Subarray (LC 152) — uses a similar left-right pass idea.

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 can't we use division?

Division by zero is undefined, and the array can contain zeros. Even without zeros, division introduces floating-point imprecision if we're not careful.

Does this handle negative numbers?

Yes — we're multiplying integers, and the sign propagates correctly through prefix and suffix products without any special handling.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →