Skip to main content

238. Product of Array Except Self

mediumAsked at Shopify

Shopify likes Product of Array Except Self because the constraint 'no division, O(n) time' forces candidates to invent the prefix/suffix pattern from scratch. It's also a stand-in for analytics pipelines where you need 'total minus this slice' fast.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Backend Developer + Senior Engineering interviews include this with the no-division constraint.
  • Reddit r/cscareerquestions (2025-10)— Shopify SWE interview reports cite this as a medium-round prefix/suffix question.

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 algorithm must run in O(n) time without using division.

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. Brute-force nested loops

For each i, multiply every other element.

Time
O(n^2)
Space
O(1) excluding output
function productExceptSelfBrute(nums) {
  const out = new Array(nums.length);
  for (let i = 0; i < nums.length; i++) {
    let p = 1;
    for (let j = 0; j < nums.length; j++) {
      if (i !== j) p *= nums[j];
    }
    out[i] = p;
  }
  return out;
}

Tradeoff: Quadratic. n = 10^5 means 10^10 operations — won't finish. Mention it only to motivate the prefix/suffix trick.

2. Prefix and suffix arrays

Build prefix[i] = product of nums[0..i-1] and suffix[i] = product of nums[i+1..n-1]. answer[i] = prefix[i] * suffix[i].

Time
O(n)
Space
O(n)
function productExceptSelfArrays(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];
  const out = new Array(n);
  for (let i = 0; i < n; i++) out[i] = prefix[i] * suffix[i];
  return out;
}

Tradeoff: Cleanest correct version. Three linear passes, O(n) extra space for prefix and suffix. Ship this if the follow-up about O(1) extra space hasn't come up yet.

3. Single output array (O(1) extra space, optimal)

First pass: out[i] holds the prefix product up to i-1. Second pass right-to-left maintaining a running suffix product; multiply out[i] by it on the fly.

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

Tradeoff: Shopify's expected answer. Output array isn't counted as extra space by convention. Two passes, no auxiliary arrays. The trick: store prefix products in the output array on pass 1, then multiply in the running suffix on pass 2.

Shopify-specific tips

Shopify's interviewer will explicitly tell you no division allowed. The O(1) extra space follow-up is almost guaranteed — if you write the O(n)-space version first, they will ask 'can you do it in O(1)?' Save time by jumping to the in-place version right after explaining the prefix/suffix idea.

Common mistakes

  • Using division — fails the constraint AND fails on inputs containing zeros.
  • Forgetting the zero edge case: [0,2] -> [2,0]; [0,0,3] -> [0,0,0]. The prefix/suffix approach handles this naturally; division-based approaches need a zero-count branch.
  • Off-by-one on the prefix range: prefix[i] should be the product of nums[0..i-1], NOT including nums[i].
  • Initializing prefix[0] or out[0] to something other than 1.

Follow-up questions

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

  • Same problem but with one element allowed to be zero (or two — handle both with a zero-count trick).
  • What if the input is a stream (online version)?
  • Generalize to 2D arrays — product of all elements in the matrix except the (i,j) cell.
  • What if integer overflow is a concern? (BigInt or modular arithmetic.)

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 isn't division allowed?

Two reasons: (1) inputs may contain zero, breaking division for at least one cell; (2) division on integers loses precision or requires modular inverse, which adds complexity. The constraint forces the prefix/suffix invention.

Does the output array count as extra space?

By convention on LeetCode and at Shopify, no — the output is required. 'O(1) extra space' here means no auxiliary arrays beyond the output. The interviewer will confirm if you ask.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →