Skip to main content

21. Product of Array Except Self

mediumAsked at Glassdoor

Glassdoor's salary-normalization pipeline needs per-element context built from all other values — this prefix-suffix product pattern is their benchmark for candidates who can think about array transformations without touching division.

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

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]. 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 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. Etc.

Example 2

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

Approaches

1. Brute force — nested loops

For each element, multiply all other elements. O(n^2) — fails at 10^5.

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

Tradeoff:

2. Prefix and suffix products

First pass builds prefix products left-to-right into the answer array. Second pass multiplies in suffix products right-to-left using a single running variable. O(n) time, O(1) extra space (output array excluded).

Time
O(n)
Space
O(1)
function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);

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

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

  return result;
}

Tradeoff:

Glassdoor-specific tips

Glassdoor interviewers almost always add the no-division constraint, so solve it that way from the start — don't volunteer a division solution and then pivot. Walk through the two-pass logic verbally: 'the left pass gives me everything to the left; the right pass folds in everything to the right.' That framing shows you understand prefix-suffix decomposition as a general technique, not a memorized trick.

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

Practice these live with InterviewChamp.AI →