Skip to main content

238. Product of Array Except Self

mediumAsked at Glean

Glean tests prefix/suffix product reasoning here — the same divide-and-accumulate pattern used in precomputing cumulative document scores across a corpus segment without redundant recalculation.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2025-12)— Glean onsite reports flag Product of Array Except Self as a strong signal-to-noise problem that reveals prefix-scan intuition.
  • Blind (2025-09)— Listed in Glean SWE prep threads as a medium that separates candidates who reach for division from those who think in prefix products.

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: Any position that doesn't include the 0 at index 2 gets a zero product.

Approaches

1. Prefix and suffix arrays

Build a prefix product array (product of all elements to the left) and a suffix product array (product of all elements to the right). 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: O(n) time, O(n) extra space. Clear and easy to reason about. Good first answer — then offer to reduce to O(1) extra space.

2. O(1) space (running suffix)

Compute the prefix products directly into the answer array. Then do a second right-to-left pass, maintaining a running suffix product and multiplying it into the answer 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);
  // left pass: answer[i] = product of nums[0..i-1]
  for (let i = 1; i < n; i++) answer[i] = answer[i - 1] * nums[i - 1];
  // right 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 by using the output array for the prefix pass and a single running variable for the suffix pass. This is the polished answer Glean expects.

Glean-specific tips

State the constraint upfront and frame your solution around it: 'No division, so I can't just compute the total product and divide — I need to think in prefix and suffix products.' Glean values candidates who acknowledge constraints before coding, not after. Present the two-array version for clarity, then say you can optimize to O(1) extra space with a running suffix variable.

Common mistakes

  • Using division — explicitly forbidden by the problem and breaks on zero elements.
  • Building prefix[i] as product including nums[i] instead of excluding it — prefix[i] should be the product of nums[0..i-1], not nums[0..i].
  • Off-by-one in suffix loop — suffix[n-1] = 1 (nothing to the right of the last element).
  • Forgetting zeros — multiple zeros in the input create all-zero outputs except possibly one position; the prefix/suffix approach handles this automatically without special-casing.

Follow-up questions

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

  • What if the array can contain only zeros — does the approach change?
  • Maximum Product Subarray (LC 152) — a related product problem requiring both max and min tracking.
  • How would you handle very large arrays where intermediate products overflow 64-bit integers?

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?

By convention, the output array that the problem asks you to return is not counted in the space complexity. Only auxiliary data structures beyond the input and output count.

What happens with two zeros in the input?

Every prefix or suffix product that crosses either zero becomes zero. The result is all zeros — no position can have a non-zero product when there are at least two zeros.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →