medium

Product of Array Except Self

Return an array where each element is the product of every other element, without using division.

1. Define the problem

Product of Array Except Self

Given an integer array nums, return an array answer such that answeri is equal to the product of every element of nums except numsi , without using division. Build a running product from the left and a running product from the right (a prefix and a suffix), and multiply them at each index.

Constraints

  • 2 ≤ nums.length ≤ 105
  • -30 ≤ numsi ≤ 30

Example

Inputnums = [1, 2, 3, 4]
Output[24, 12, 8, 6]

Explanation answer0 = 2*3*4 = 24, answer1 = 1*3*4 = 12, answer2 = 1*2*4 = 8, answer3 = 1*2*3 = 6.

2. Visualize the solution

Multiply a left-to-right product by a right-to-left product

Multiply a left-to-right product by a right-to-left product
Statusleft-pass

Pass 1 fills each slot with the product of everything before it: [1, 1, 2, 6].

What happens in this step

leftProduct = 1
i=0: result[0] = 1;              leftProduct *= 1 → 1
i=1: result[1] = 1;              leftProduct *= 2 → 2
i=2: result[2] = 2;              leftProduct *= 3 → 6
i=3: result[3] = 6;              leftProduct *= 4 → 24

after pass 1: result = [1, 1, 2, 6]
Step 1 of 3

Steps to visualize

  1. Pass 1: walk left to right, storing the running product of everything before each index into the answer array.
  2. Pass 2: walk right to left, multiplying each answer entry by the running product of everything after that index.
  3. Every index now holds the product of everything except itself.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Multiply a left-to-right product by a right-to-left product
Statusleft-pass

Pass 1 fills each slot with the product of everything before it: [1, 1, 2, 6].

What happens in this step

leftProduct = 1
i=0: result[0] = 1;              leftProduct *= 1 → 1
i=1: result[1] = 1;              leftProduct *= 2 → 2
i=2: result[2] = 2;              leftProduct *= 3 → 6
i=3: result[3] = 6;              leftProduct *= 4 → 24

after pass 1: result = [1, 1, 2, 6]
Step 1 of 3
4. Solution

Solution

solution.tsTypeScript
function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);

  let leftProduct = 1;
  for (let i = 0; i < n; i++) {
    result[i] = leftProduct;
    leftProduct *= nums[i];
  }

  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= rightProduct;
    rightProduct *= nums[i];
  }

  return result;
}
Time
O(n)
Space
O(1) extra, excluding the output array
5. Test cases

Test cases

InputExpectedCovers
nums = [1, 2, 3, 4][24, 12, 8, 6]example from the docstring
nums = [-1, 1, 0, -3, 3][0, 0, 9, 0, 0]a single zero forces most outputs to zero without dividing
nums = [1, 1, 1, 1][1, 1, 1, 1]every value is one, no change in magnitude
nums = [3, 5][5, 3]smallest valid input, exactly two elements
nums = [-1, -1, -1, -1][-1, -1, -1, -1]all-negative values, sign handled correctly
nums = [0, 4, 0][0, 0, 0]two zeros make every product zero

Keep reading

TopicDescription
Prefix SumPrecompute running totals so the sum of any range can be answered instantly instead of adding it up every time.
Running Sum of 1d ArrayReturn a new array where each element is the sum of all elements up to that point.
Find Pivot IndexFind the index where the sum of numbers to the left equals the sum of numbers to the right.
Subarray Sum Equals KCount how many contiguous subarrays add up to a target value.
Contiguous ArrayFind the longest contiguous subarray with an equal number of 0s and 1s.
Range Sum Query 2D - ImmutableAnswer repeated queries for the sum of values inside a rectangle of a fixed grid.