Product of array except self

Medium TimeO(n) SpaceO(1) extra

Given an array of integers nums, return an array in which each position holds the product of every other value — for [1, 2, 3, 4] that is [24, 12, 8, 6]. Division may not be used, and the array may contain a zero.

Examples

Example 1

Input
nums = [1, 2, 3, 4]
Output
[24,12,8,6]
Position 2 holds 1 × 2 × 4 = 8 — its own 3 is the one value left out.

Example 2

Input
nums = [2, 0, 3]
Output
[0,6,0]
A zero makes every other position 0, and its own position the product of the rest: 2 × 3 = 6.

The Code

function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    result[i] = prefix;
    prefix *= nums[i];
  }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= suffix;
    suffix *= nums[i];
  }
  return result;
}
productExceptSelf([1, 2, 3, 4]);
Done
Step through productExceptSelf([1, 2, 3, 4]) call by call

Explanation

Each answer is everything to the left of a position multiplied by everything to its right — for position 2 in [1, 2, 3, 4] that is (1 × 2) × 4 = 8. Neither half has to be worked out from scratch at each position: one walk from the left carries the left-hand product along in prefix, and one back from the right carries the other in suffix, which is why nothing ever has to be divided out.

  1. 1

    prefix holds the product of everything to the left of i, and starts at 1. At position 0: result[0] takes that 1, since nothing lies to its left — then nums[0], which is 1, multiplies into prefix, leaving it at 1.

    nums
    1
    2
    3
    4
    result
    i
    1
    0
    1
    1
    1
    2
    1
    3

    prefix=1

    result[0] = 1 · prefix stays 1

  2. 2

    At position 1: result[1] takes the current prefix, which is 1 — everything to the left of position 1 is just that first 1. Then nums[1], the 2, multiplies into prefix.

    nums
    1
    2
    3
    4
    result
    1
    0
    i
    1
    1
    1
    2
    1
    3

    prefix=1

    result[1] = 1 · prefix → 2

  3. 3

    At position 2: result[2] takes prefix, now 2 — the 1 and the 2 behind it. Then nums[2], the 3, multiplies into prefix.

    nums
    1
    2
    3
    4
    result
    1
    0
    1
    1
    i
    2
    2
    1
    3

    prefix=2

    result[2] = 2 · prefix → 6

  4. 4

    At position 3: result[3] takes prefix, now 6. Then nums[3], the 4, multiplies into prefix — making 24, which nothing will read.

    nums
    1
    2
    3
    4
    result
    1
    0
    1
    1
    2
    2
    i
    6
    3

    prefix=6

    result[3] = 6 · prefix → 24

  5. 5

    The first pass is finished. Every position holds the product of everything before it, and nothing yet of what comes after.

    nums
    1
    2
    3
    4
    result
    1
    0
    1
    1
    2
    2
    i
    6
    3

    prefix=24

    result → [1, 1, 2, 6]

  6. 6

    The second pass walks back, and suffix holds the product of everything to the right of i, starting at 1. At position 3: result[3] is multiplied by suffix — 6 × 1, so it does not change. Then nums[3], the 4, multiplies into suffix.

    nums
    1
    2
    3
    4
    result
    1
    0
    1
    1
    2
    2
    i
    6
    3

    suffix=1

    result[3] = 6 × 1 = 6 · suffix → 4

  7. 7

    At position 2: result[2] is multiplied by suffix — 2 × 4 = 8. Then nums[2], the 3, multiplies into suffix.

    nums
    1
    2
    3
    4
    result
    1
    0
    1
    1
    i
    8
    2
    6
    3

    suffix=4

    result[2] = 2 × 4 = 8 · suffix → 12

  8. 8

    At position 1: result[1] is multiplied by suffix — 1 × 12 = 12. Then nums[1], the 2, multiplies into suffix.

    nums
    1
    2
    3
    4
    result
    1
    0
    i
    12
    1
    8
    2
    6
    3

    suffix=12

    result[1] = 1 × 12 = 12 · suffix → 24

  9. 9

    At position 0: result[0] is multiplied by suffix — 1 × 24 = 24. That is the last position, and the pass ends.

    nums
    1
    2
    3
    4
    result
    i
    24
    0
    12
    1
    8
    2
    6
    3

    suffix=24

    result[0] = 1 × 24 = 24

  10. 10

    Each position has been written once with everything to its left and multiplied once by everything to its right, and never by the value sitting on it.

    nums
    1
    2
    3
    4
    result
    24
    0
    12
    1
    8
    2
    6
    3

    [24, 12, 8, 6]

More like this

All arrays & loops examples (10) →