Skip to main content

238. Product of Array Except Self

mediumAsked at LinkedIn

Compute the product of every array element except the current one — without division — using prefix and suffix passes. LinkedIn asks this to test whether you can reason about O(n) algorithms under artificial constraints, mirroring how their data pipeline computes per-member aggregates that exclude the member's own data.

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 elements of nums except nums[i]. The algorithm must run in O(n) time and must not use 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: answer[0]=2*3*4=24, answer[1]=1*3*4=12, answer[2]=1*2*4=8, answer[3]=1*2*3=6.

Example 2

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

Approaches

1. Division with zero handling — not allowed but worth naming

Compute total product, then divide by each element. Breaks on zeros and violates the no-division constraint. State this to show awareness of the trap, then discard it.

Time
O(n)
Space
O(1)
// NOT valid per constraints — shown only to motivate the prefix/suffix approach:
// totalProduct / nums[i] fails for zeros and violates the no-division rule.

Tradeoff:

2. Prefix + suffix arrays — two passes

First pass builds prefix[i] = product of nums[0..i-1]. Second pass builds suffix[i] = product of nums[i+1..n-1]. answer[i] = prefix[i] * suffix[i]. Two O(n) passes, O(n) extra space.

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:

LinkedIn-specific tips

LinkedIn consistently asks for the O(1) extra-space follow-up: 'can you do it without the suffix array?' The answer is to fold the suffix into the output array in a single right-to-left pass after filling it with prefix products. Mention this optimization unprompted — it signals you think about memory as a first-class resource. The zero-count trick (count zeros to handle zero-product edge cases) is a common distraction; the prefix/suffix approach handles zeros naturally without any special casing.

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

Practice these live with InterviewChamp.AI →