Skip to main content

19. Product of Array Except Self

mediumAsked at N26

Return an array where each element is the product of every other element, without division and in O(n). N26 uses it to test prefix/suffix discipline before harder running-balance ledger questions.

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 do it without division and in O(n) time.

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • 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. Nested loops

For each index, multiply all the other elements.

Time
O(n^2)
Space
O(n)
const ans = new Array(nums.length).fill(1);
for (let i=0;i<nums.length;i++)
  for (let j=0;j<nums.length;j++)
    if (i!==j) ans[i] *= nums[j];

Tradeoff:

2. Prefix and suffix products

First pass fills ans[i] with the product of everything to the left. Second pass multiplies in the running product from the right. Uses O(1) extra space beyond the output.

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

Tradeoff:

N26-specific tips

N26 grades you on noticing that the same prefix/suffix dance powers their running-balance widget - every transaction needs balance-before and balance-after computed in one pass over the daily ledger.

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

Practice these live with InterviewChamp.AI →