Skip to main content

19. Product of Array Except Self

mediumAsked at Coupang

Compute the product of all elements except each index without division, mirroring how Coupang's recommendation system computes per-SKU lift signals while excluding the current item from the cohort.

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

Problem

Given an integer array nums, return an array answer such that answer[i] equals the product of all elements except nums[i]. Solve in O(n) time without using division.

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • the product of any prefix or suffix fits 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. Prefix + suffix arrays

Build left-products and right-products in separate arrays; multiply pointwise.

Time
O(n)
Space
O(n)
const left = [], right = [];
left[0] = 1; for (let i = 1; i < n; i++) left[i] = left[i-1] * nums[i-1];
right[n-1] = 1; for (let i = n-2; i >= 0; i--) right[i] = right[i+1] * nums[i+1];
return left.map((v, i) => v * right[i]);

Tradeoff:

2. Two-pass with O(1) extra

First pass writes prefix products into the answer; second pass walks right-to-left multiplying a running suffix.

Time
O(n)
Space
O(1) extra
function productExceptSelf(nums) {
  const n = nums.length, 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:

Coupang-specific tips

Coupang's recommendation system computes per-SKU lift while excluding the current item from the cohort; the two-pass O(1) approach matches the bounded-memory pattern their batch scoring jobs use.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →