Skip to main content

238. Product of Array Except Self

mediumAsked at Linear

Return an array where each element is the product of all other elements, without using division and in O(n). Linear asks this to see if you can find the 'prefix and suffix product' insight — a classic example of precomputed auxiliary arrays.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Frequently cited in Linear SWE onsite reports as a no-division array problem.
  • Blind (2025-11)— Multiple Linear interview threads list this as a benchmark for prefix-array thinking.

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]

Example 2

Input
nums = [-1,1,0,-3,3]
Output
[0,0,9,0,0]

Approaches

1. Division approach (not allowed)

Compute total product, divide by each element. Breaks on zeros and is explicitly disallowed by the problem.

Time
O(n)
Space
O(1)
// This approach is INVALID per problem constraints (no division allowed)
// Shown for contrast only
function productExceptSelf(nums) {
  const total = nums.reduce((a, b) => a * b, 1);
  return nums.map(n => total / n);
}

Tradeoff: Fails on zeros and violates the no-division constraint. Mention it only to explain why it doesn't work before presenting the correct approach.

2. Prefix and suffix arrays

Build a prefix-product array and a suffix-product array. answer[i] = prefix[i-1] * suffix[i+1].

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 nums.map((_, i) => prefix[i] * suffix[i]);
}

Tradeoff: O(n) time and O(n) space. Clear and correct. Most Linear interviewers accept this.

3. O(1) extra space (optimal)

Reuse the output array for prefix products, then do a right-to-left pass maintaining a running suffix product.

Time
O(n)
Space
O(1)
function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    result[i] = prefix;
    prefix *= nums[i];
  }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= suffix;
    suffix *= nums[i];
  }
  return result;
}

Tradeoff: O(1) extra space (the output array doesn't count). First pass fills result with prefix products; second pass multiplies in suffix products using a running variable.

Linear-specific tips

The no-division constraint is the signal — it forces you toward the prefix/suffix pattern. State this connection explicitly: 'Since division is banned, I need answer[i] = (product of everything left) * (product of everything right), which is prefix times suffix.' Then mention the O(1) space optimization — building prefix in-place and sweeping suffix right-to-left.

Common mistakes

  • Using division — explicitly banned by the problem statement.
  • Allocating two full O(n) arrays when only two scalar accumulators are needed in the O(1) approach.
  • Not handling zeros — the no-division approach handles zeros naturally since you never actually divide.

Follow-up questions

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

  • What if the problem allowed division? How would you handle arrays containing zeros?
  • Maximum Product Subarray (LC 152) — related product pattern but requires tracking both min and max.
  • Can you solve this if nums can contain very large numbers that overflow?

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 doesn't the output array count as extra space?

By convention, the output (return value) is excluded from the auxiliary space count. The O(1) solution uses the output array cleverly but allocates nothing else.

What if nums contains a zero?

No division means no division-by-zero issue. The prefix/suffix pass correctly propagates the zero through the products.

Why two passes?

One left-to-right pass computes all left products; one right-to-left pass computes all right products. Their element-wise product is the answer.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →