Skip to main content

16. Product of Array Except Self

mediumAsked at LINE

For each index, return the product of every other element without using division — LINE uses this to test prefix/suffix-pass thinking, the same backbone of their read-receipt aggregation.

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

Problem

Given an integer array nums, return an array answer such that answer[i] is the product of all elements of nums except nums[i]. Solve without division and in O(n) time. The product of any prefix or suffix fits in a 32-bit integer.

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30

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 i, multiply every other index.

Time
O(n^2)
Space
O(n)
for(let i=0;i<n;i++){
  let p=1;
  for(let j=0;j<n;j++) if(j!==i) p*=nums[j];
  out[i]=p;
}

Tradeoff:

2. Prefix and suffix passes

First left-to-right pass stores prefix products into the output. Second right-to-left pass multiplies a running suffix product into each cell. Two passes, no division.

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

Tradeoff:

LINE-specific tips

At LINE, link the two-pass prefix/suffix shape to aggregating read-receipt deltas across a chat room while excluding the sender — presence + read-receipt framing wins.

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

Practice these live with InterviewChamp.AI →