#238 - Product of Array Except Self

MediumArray / String

Given an integer array nums, return an array answer where answer[i] equals the product of all elements of nums except nums[i]. You must solve it without using division and in O(n) time. The output array does not count as extra space.

Input	Output
nums = [1,2,3,4]	[24,12,8,6]
nums = [-1,1,0,-3,3]	[0,0,9,0,0]

Solution Space

Try it

/**
 * Computes the product of every element except self without division.
 * Uses the output array to store prefix products, then a single
 * backward pass multiplies in the suffix products.
 *
 * @param nums  Array of integers (length >= 2)
 * @returns     Product-except-self array
 */
export function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array<number>(n);

  // answer[i] = product of all elements to the LEFT of i
  answer[0] = 1;
  for (let i = 1; i < n; i++) {
    answer[i] = answer[i - 1] * nums[i - 1];
  }

  // Multiply in products from the RIGHT using a running suffix
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }

  return answer;
}

Approach: prefix-suffix product (single output array) – compute prefix products in the first pass, then multiply by suffix products in a reverse pass.

Time: O(n) – two passes through the array.

Space: O(1) extra – output array doesn't count per the problem statement.

Alternative approaches:

Approach	Idea	Time	Space
Two separate arrays	Build explicit prefix[] and suffix[] arrays, then multiply	O(n)	O(n) extra
Division (if allowed)	Compute total product, divide by each element (handle zeros carefully)	O(n)	O(1)

Why the single-array prefix-suffix method is preferred:

• Meets the no-division constraint and uses no extra space beyond the output.
• Two clean passes make it easy to reason about correctness.

#151 Reverse Words in a String

#334 Increasing Triplet Subsequence