Skip to main content

18. Product of Array Except Self

mediumAsked at Byju's

Return an array where each index holds the product of every other element, 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. The product of any prefix or suffix is guaranteed to fit in a 32-bit integer.

Constraints

  • 2 <= nums.length <= 10^5
  • Product of any prefix/suffix fits in 32-bit signed int

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 product

For each index multiply every other element in the array.

Time
O(n^2)
Space
O(n)
const r=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) r[i]*=nums[j];
return r;

Tradeoff:

2. Prefix and suffix products

Build prefix products in one pass and multiply by running suffix products in a reverse pass. Output array doubles as workspace.

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

Tradeoff:

Byju's-specific tips

Byju's interviewers like prefix/suffix walkthroughs because the pattern shows up in their adaptive-learning learner-aggregate scoring service.

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

Practice these live with InterviewChamp.AI →