Product of Array Except Self

MediumArrays & HashingArrayPrefix Sum

Problem

You are given an integer array. Return a new array where each position holds the product of every other element, excluding the value at that position itself. The solution may not use division.

Example. For [1, 2, 3, 4], the answer is [24, 12, 8, 6]: position 0 excludes the 1, giving 2 × 3 × 4 = 24, and so on for each position.

Key idea

Recomputing the product of the other elements from scratch at every position costs O(n²). If division were allowed, the total product could be computed once and divided by each element, but the problem rules that out, and it would break anyway whenever the array contains a zero.

The product excluding position i is exactly the product of everything before i times the product of everything after i. That splits the work into two simpler passes: first sweep left to right, storing at each position the running product of elements seen strictly before it; then sweep right to left, tracking a running product of elements strictly after the current position, and multiply that into the value already stored there. The running suffix product can be a single variable rather than a second array.

Solution

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array<number>(n).fill(1);

  let prefix = 1;
  for (let i = 0; i < n; i++) {
    result[i] = prefix; // product of everything strictly before i
    prefix *= nums[i];
  }

  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= suffix; // fold in the product of everything strictly after i
    suffix *= nums[i];
  }

  return result;
}

Complexity

  • Time: O(n). Two linear passes over the array.
  • Space: O(1) extra. Beyond the required output array, only a running suffix product variable is needed.

Watch out for

  • Zeros need no special casing if the prefix/suffix approach is used correctly: a single zero makes every other position's product zero automatically, since the zero contributes to either the prefix or suffix product at every other index.
  • Do not reach for division as a shortcut, it fails outright whenever any element is zero and is disallowed by the problem regardless.
  • Keep the two passes distinct: build the prefix products fully before layering in the suffix pass, so no needed prefix value gets overwritten early.

Pattern

This is the prefix/suffix aggregation pattern: precompute cumulative information from the left and separately from the right, then combine the two at each index. The same shape shows up whenever a problem needs "everything before" and "everything after" a position simultaneously.

Related questions