Skip to main content

238. Product of Array Except Self

mediumAsked at Citadel

This problem prohibits division and demands O(1) extra space (excluding output) — a tight constraint that forces a prefix/suffix product pattern. At Citadel, this mental model maps to computing rolling window statistics on time-series data while excluding the current observation. The constraint bar is a deliberate filter.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2025-12)— Citadel SWE candidates cite Product of Array Except Self as a problem specifically used to test whether candidates can meet multiple simultaneous constraints.
  • Blind (2025-10)— Citadel threads note this problem's 'no division' constraint is the key filter — candidates who miss it are flagged immediately.

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: For index 0: 2*3*4=24. For index 1: 1*3*4=12. For index 2: 1*2*4=8. For index 3: 1*2*3=6.

Example 2

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

Explanation: The zero makes most products zero; index 2 gets (-1)*1*(-3)*3=9.

Approaches

1. Prefix + suffix products (two passes, O(1) extra space)

First pass: fill output[i] with the product of all elements to the left of i. Second pass: multiply output[i] by the running product of all elements to the right of i.

Time
O(n)
Space
O(1) extra (output array not counted)
function productExceptSelf(nums) {
  const n = nums.length;
  const output = new Array(n);

  // Forward pass: output[i] = product of nums[0..i-1]
  output[0] = 1;
  for (let i = 1; i < n; i++) {
    output[i] = output[i - 1] * nums[i - 1];
  }

  // Backward pass: multiply by product of nums[i+1..n-1]
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    output[i] *= suffix;
    suffix *= nums[i];
  }

  return output;
}

Tradeoff: O(n) time, O(1) extra space (the output array is required by the problem spec and not counted). Two passes, no division. This is the canonical O(1)-space answer Citadel expects.

Citadel-specific tips

Before writing any code, acknowledge all three constraints out loud: 'O(n) time — no nested loops. No division — can't do totalProduct / nums[i]. O(1) extra space — no separate prefix and suffix arrays.' This constraint-awareness is what Citadel grades first. Then explain: 'I'll store prefix products in the output array during the forward pass, then multiply by suffix products in a single variable during the backward pass.' Expect the follow-up: 'What if nums contains zeros?' — the prefix/suffix approach handles zeros correctly without special-casing because products naturally become 0 when the zero is included in the scan.

Common mistakes

  • Allocating separate prefix and suffix arrays — correct but uses O(n) extra space, violating the constraint.
  • Attempting totalProduct / nums[i] — division is explicitly prohibited and breaks on zeros anyway.
  • Not initializing output[0] = 1 in the forward pass — the prefix product of zero elements is 1 (the multiplicative identity).
  • Forgetting to initialize suffix = 1 before the backward pass — starting with suffix = nums[n-1] causes an off-by-one.

Follow-up questions

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

  • What if the problem allowed division? (Handle zeros: one zero → all others get 0, the zero index gets total product. Two zeros → all zeros.)
  • How would you extend this to a sliding-window product (product of last k elements)?
  • Trapping Rain Water (LC 42) uses a similar prefix-max + suffix-max pattern — can you see the connection?

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 division work when there are zeros?

You can't divide by zero. Even if you handle zeros specially, you need a separate branch for one-zero and two-zero cases — messier than the prefix/suffix approach which handles them naturally.

Why is the output array not counted in the space complexity?

The problem requires returning an array of the same length as the input. This is considered required output space, not auxiliary space. O(1) extra space means no additional arrays beyond the output.

What does 'product of zero elements' equal?

1 — the multiplicative identity. This is why output[0] starts at 1 (no elements to its left) and suffix starts at 1 (no elements to the right of the last element).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →