Skip to main content

19. Product of Array Except Self

mediumAsked at Electronic Arts

Compute for each position the product of all other elements without division, a prefix/suffix technique EA applies in simulation stat calculations and damage multiplier systems.

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 product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. 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
  • The product of any prefix or suffix of nums is guaranteed to fit 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. Two-pass with separate prefix/suffix arrays

Build a left-products array and a right-products array, then multiply them element-wise.

Time
O(n)
Space
O(n)
function productExceptSelf(nums) {
  const n = nums.length;
  const left = new Array(n).fill(1), right = new Array(n).fill(1), res = [];
  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];
  for (let i = 0; i < n; i++) res.push(left[i] * right[i]);
  return res;
}

Tradeoff:

2. O(1) extra space with running suffix

Build the left-product in-place into the output array, then do a second right-to-left pass multiplying a running suffix variable. This avoids the extra right[] array and is the space-optimal solution EA interviewers check for.

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

Tradeoff:

Electronic Arts-specific tips

EA interviews cover game development data structures, pathfinding (A*, BFS on grids), spatial algorithms, and simulation problems. Grid/matrix manipulation and BFS on 2D arrays are very common.

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

Practice these live with InterviewChamp.AI →