Product of Array Except SelfMedium

Given an array nums, return an array where output[i] is the product of every element except nums[i]. Must run in O(n) time, and you cannot use division.

Examples

Input: nums = [1,2,3,4] → Output: [24,12,8,6]

Approach

The 'no division' constraint rules out the obvious shortcut (multiply everything, then divide by nums[i]) — plus that shortcut breaks entirely if any element is zero. The real approach: output[i] is just (product of everything left of i) × (product of everything right of i). Compute prefix products in one left-to-right pass, storing them directly into the result array, then fold in suffix products with a second right-to-left pass. No extra array needed beyond the output itself.

Complexity — best & worst case

Brute force — time O(n²) — for every index, multiply the rest of the array

Optimal — time O(n), best and worst case are the same — two full passes, always

Optimal — space O(1) extra, not counting the output array

Code

// Given an array nums, return an array where output[i] is the
// product of every element except nums[i]. Must run in O(n) and
// you CANNOT use division.

// --- Brute force: for each index, multiply everything else ---
// (violates the O(n) requirement, but it's the obvious first idea)
function productExceptSelfBrute(nums) {
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    let product = 1;
    for (let j = 0; j < nums.length; j++) {
      if (i !== j) product *= nums[j];
    }
    result.push(product);
  }
  return result;
}

// --- Optimal: prefix products going left-to-right, then fold in
// suffix products going right-to-left. Two O(n) passes, no division. ---
function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);

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

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

  return result;
}

// --- Example Usage ---
console.log(productExceptSelf([1, 2, 3, 4])); // [24, 12, 8, 6]
console.log(productExceptSelfBrute([1, 2, 3, 4])); // [24, 12, 8, 6]
console.log(productExceptSelf([-1, 1, 0, -3, 3])); // [-0, 0, 9, -0, 0] (0 * a negative = -0 in JS; -0 === 0, harmless)