Skip to main content

238. Product of Array Except Self

mediumAsked at Hugging Face

Compute for each index the product of all other elements without using division. Hugging Face uses this to test prefix/suffix scan thinking — the same forward-backward pass pattern that computes gradient accumulation across a sequence in backpropagation through time.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2025-12)— Cited in Hugging Face onsite reports as a medium problem probing prefix-scan and in-place optimization.
  • Blind (2025-10)— Hugging Face threads list this as a signal problem for ML engineers who understand forward-backward computation patterns.

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: Zero propagates — any product including the zero position is zero.

Approaches

1. Prefix and suffix arrays

Build a prefix-product array (left[i] = product of all elements before i) and a suffix-product array (right[i] = product of all elements after i). 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 nums.map((_, i) => left[i] * right[i]);
}

Tradeoff: O(n) time, O(n) space (two extra arrays). Clear and easy to explain. Start here to establish correctness, then optimize.

2. O(1) extra space (output array as prefix)

Use the output array as the prefix array. Then make a single right-to-left pass with a running suffix product, multiplying into the output in place.

Time
O(n)
Space
O(1) extra (output array doesn't count)
function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  // Forward pass: answer[i] = product of nums[0..i-1]
  for (let i = 1; i < n; i++) answer[i] = answer[i-1] * nums[i-1];
  // Backward pass: multiply in suffix product
  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 doesn't count per the problem statement. This is the expected optimal answer. The forward-backward pattern directly mirrors the forward-backward passes in sequence model training.

Hugging Face-specific tips

Lead with the two-array approach to demonstrate correctness, then say: 'I can eliminate one array by using the output array as the prefix and computing the suffix on the fly in the backward pass.' Hugging Face engineers appreciate when you connect this to ML: 'This forward-backward scan is structurally identical to how gradients accumulate in backpropagation through time — the prefix pass is the forward computation and the suffix pass is the backward gradient flow.' This connection consistently impresses ML-focused interviewers.

Common mistakes

  • Using division — explicitly banned. Handle zeros separately with division is also incorrect for multiple zeros.
  • Off-by-one in the prefix array — left[i] should be the product of elements BEFORE i (not including i).
  • Forgetting to initialize left[0] = 1 and right[n-1] = 1 (empty prefix/suffix products are 1).
  • Not initializing the suffix variable to 1 in the space-optimized approach.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • What if the array can contain zeros? How does that affect your approach? (The algorithm handles it correctly — test with [0,1,2] and [-1,0,3].)
  • Can you do this in O(1) space if division is allowed? (Yes — divide total product by nums[i], but handle zeros.)
  • How would you compute prefix products in parallel across a distributed array partitioned across machines?

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 output array not counted as extra space?

The problem requires returning an output array, so that space is inherent to the output and excluded from the space complexity calculation.

How does the algorithm handle zeros?

Correctly — if nums[i] is zero, the prefix product up to i and suffix product from i each propagate 0 to adjacent positions, giving the right results without special-casing.

What is the forward-backward pattern's connection to ML?

The prefix (left) pass is analogous to the forward pass computing hidden states; the suffix (right) pass is analogous to the backward pass computing gradients. Both are O(n) one-directional scans combined to get per-element information.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →