Skip to main content

93. Product of Array Except Self

mediumAsked at Ola

Compute an array where each index is the product of all others.

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]. The algorithm must run in O(n) and you cannot use division.

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The product fits 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. Total product then divide

Compute the product of all numbers and divide by each element.

Time
O(n)
Space
O(n)
// disallowed by problem; also fails on zeros

Tradeoff:

2. Two prefix passes

First pass writes prefix products; second pass multiplies by suffix product accumulated in a single variable.

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

Tradeoff:

Ola-specific tips

Ola tests prefix/suffix discipline; tie it to computing per-driver weighted scores by everyone-else aggregates without iterating twice quadratically.

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

Practice these live with InterviewChamp.AI →