Product of Array Except Self

The problem

Given a list of integers nums, return a list of the same length in which each entry is the product of all the numbers in nums except the one at that position. You may not use division.

What to write

function solve(nums: number[]): number[]

Input
nums = [1,2,3,4]

Output
[24,12,8,6]

Input
nums = [0,1,2,3]

Output
[6,0,0,0]

Constraints

2–100 integers; all products are safe JavaScript integers; division forbidden.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Division is forbidden, so you cannot multiply everything together and divide each number out. Recomputing every product from scratch works, but it repeats the same multiplications again and again.

2. Hint 2: Ask a smaller question

   Take the list 1, 2, 3, 4. Write out what you multiply for position 1, then for position 2. Which numbers appear in both products, and could that part of the work be shared?

3. Hint 3: Name the pattern

   The answer at a position is the product of everything before it times the product of everything after it. Running products give you both: one pass from the left, one from the right. These are prefix and suffix passes. Read the lesson on prefix and suffix passes.

4. Hint 4: State the invariant

   During the left-to-right pass, the running product is always the product of all numbers before the current position. During the right-to-left pass, it is the product of all numbers after it.

5. Hint 5: Sketch the pseudocode

   Make a list of ones. Go left to right with a running product p = 1: write p into the slot, then multiply p by the number. Go right to left with p = 1 again: multiply the slot by p, then multiply p by the number.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Store the product of values before each index. Walk backward multiplying by the product after each index, so no division is needed.

The slow way

For each position, multiply all the other numbers together. It is correct, but every position repeats almost the same multiplications: n positions times n numbers is n × n steps.

The insight

The product of all the others is the product of everything to the left times the product of everything to the right. Both can be carried along as running products, so each position costs three multiplications instead of about n.

Step by step

1. Start an answer list with one slot per number. The answer has one entry per number. The first pass overwrites every slot, so the starting value, 1 here, does not matter.
2. Going right, give each slot the product of everything before it. The running product is written into the slot before the current number is multiplied in, so the slot gets only the numbers before it.
3. Going left, multiply in the product of everything after it. The same idea from the other side: the slot is multiplied by the running product first, and only then is the current number multiplied into the running product. So the slot gets only the numbers after it.
4. Each slot now holds the product of all the other numbers. Each slot was multiplied by everything before its position and everything after it, and never by its own number.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Start an answer list with one slot per number
  const out = Array(nums.length).fill(1);
  // 2. Going right, give each slot the product of everything before it
  let product = 1;
  for (let i = 0; i < nums.length; i++) {
    out[i] = product;
    product *= nums[i];
  }
  // 3. Going left, multiply in the product of everything after it
  product = 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    out[i] *= product;
    product *= nums[i];
  }
  // 4. Each slot now holds the product of all the other numbers
  // (JavaScript can produce -0 here; it is reported as 0.)
  return out.map((x) => (x === 0 ? 0 : x));
}

function solve(nums: number[]): number[] {
  // 1. Start an answer list with one slot per number
  const out = Array(nums.length).fill(1);
  // 2. Going right, give each slot the product of everything before it
  let product = 1;
  for (let i = 0; i < nums.length; i++) {
    out[i] = product;
    product *= nums[i];
  }
  // 3. Going left, multiply in the product of everything after it
  product = 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    out[i] *= product;
    product *= nums[i];
  }
  // 4. Each slot now holds the product of all the other numbers
  // (JavaScript can produce -0 here; it is reported as 0.)
  return out.map((x) => (x === 0 ? 0 : x));
}

def solve(nums):
    # 1. Start an answer list with one slot per number
    out = [1] * len(nums)
    # 2. Going right, give each slot the product of everything before it
    product = 1
    for i, num in enumerate(nums):
        out[i] = product
        product *= num
    # 3. Going left, multiply in the product of everything after it
    product = 1
    for i in reversed(range(len(nums))):
        out[i] *= product
        product *= nums[i]
    # 4. Each slot now holds the product of all the other numbers
    return out

Example 1, traced

Input
nums = [1,2,3,4]

Output
[24,12,8,6]

Why it works

After the first pass, a slot holds the product of the numbers before it. The second pass multiplies it by the product of the numbers after it. Together that is every number except its own, and no division was used.

Time and space

Time O(n), extra space O(n) output; O(1) extra. There are two passes over the n numbers with a constant amount of work at each position, so the time is O(n). Apart from the answer list itself, only one running product is stored.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Write the running product into the slot first, and only then multiply the running product by the current number. The other order includes the number you are supposed to leave out.
• Reset the running product to 1 before the second pass. Starting it from the first pass's total multiplies every slot by the product of the whole list as well.

Pattern

Prefix and suffix passes.

Keep going