SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Product of Array Except Self Visualizer

out[i] = (product of everything left of i) × (product of everything right of i). One pass left to right stores the left products, a second pass right to left multiplies in the right products.

Start the Product of Array Except Self simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. out[0] = 1: nothing is left of index 0. [1, 2, 3, 4, 5]
  2. out[1] = out[0] × a[0] = 1, the product of everything left of 1.
  3. out[2] = out[1] × a[1] = 2, the product of everything left of 2.
  4. out[3] = out[2] × a[2] = 6, the product of everything left of 3.
  5. out[4] = out[3] × a[3] = 24, the product of everything left of 4.
  6. Left products done. Now walk back with right = 1, the product of everything to the right.
  7. out[4] × right (1) = 24. Index 4 is final.
  8. right × a[4] = 5.
  9. out[3] × right (5) = 30. Index 3 is final.
  10. right × a[3] = 20.
  11. out[2] × right (20) = 40. Index 2 is final.
  12. right × a[2] = 60.
  13. out[1] × right (60) = 60. Index 1 is final.
  14. right × a[1] = 120.
  15. out[0] × right (120) = 120. Index 0 is final.
  16. right × a[0] = 120.
  17. Done: 120, 60, 40, 30, 24.

Try it with your own input →

Product of array except self in Java, Python, C++, C and JavaScript

int[] productExceptSelf(int[] a) {
  int n = a.length;
  int[] out = new int[n];
  out[0] = 1;
  for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];
  int right = 1;
  for (int i = n - 1; i >= 0; i--) {
    out[i] *= right;
    right *= a[i];
  }
  return out;
}
def product_except_self(a):
    n = len(a)
    out = [1] * n
    for i in range(1, n):
        out[i] = out[i - 1] * a[i - 1]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= a[i]
    return out
vector<int> productExceptSelf(const vector<int>& a) {
  int n = a.size();
  vector<int> out(n);
  out[0] = 1;
  for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];
  int right = 1;
  for (int i = n - 1; i >= 0; i--) {
    out[i] *= right;
    right *= a[i];
  }
  return out;
}
void productExceptSelf(int a[], int n, int out[]) {
  out[0] = 1;
  for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];
  int right = 1;
  for (int i = n - 1; i >= 0; i--) {
    out[i] *= right;
    right *= a[i];
  }
}
function productExceptSelf(a) {
  const n = a.length;
  const out = new Array(n);
  out[0] = 1;
  for (let i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= right;
    right *= a[i];
  }
  return out;
}

In an interview

LeetCode 238, Product of Array Except Self: out[i] is the product of every value except a[i], without division.

Division fails when a value is 0, which is why the question bans it. The output array does not count as extra space, so this is O(1) extra memory.

More patterns