Skip to main content

19. Product of Array Except Self

mediumAsked at Monzo

For each transaction, compute the product of all other transaction multipliers in O(n) without 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 write an algorithm that runs in O(n) time and without using the division operation.

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • Result fits in 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 and suffix arrays

Build left[i] = product of nums[0..i-1] and right[i] = product of nums[i+1..n-1]; answer is left[i] * right[i].

Time
O(n)
Space
O(n)
const n = nums.length, left = new Array(n).fill(1), right = new Array(n).fill(1);
for (let i = 1; i < n; i++) left[i] = left[i-1] * nums[i-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. In-place running products

Fold the prefix product into the answer array, then sweep right-to-left multiplying by a running suffix.

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

Tradeoff:

Monzo-specific tips

Monzo flags the no-division constraint because division on integer pence introduces rounding that breaks ledger invariants.

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

Practice these live with InterviewChamp.AI →