Skip to main content

20. Product of Array Except Self

mediumAsked at Indeed

Compute each element's product of all other elements without using division — a prefix/suffix scan Indeed applies to confidence-score normalization across job recommendations.

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 of nums except nums[i]. You must solve it in O(n) time without using the division operation.

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. Two-pass with extra arrays

Build separate prefix and suffix product arrays then multiply them.

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:

2. O(1) extra space with running suffix

Use the output array for prefix products in one pass, then multiply in a running suffix right-to-left, eliminating the extra arrays.

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

Tradeoff:

Indeed-specific tips

Indeed grades for the O(1)-extra-space variant; framing the suffix pass as a streaming right-to-left scan over a recommendation score array earns strong domain credit.

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 Indeed interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →