#9 · Arrays & Hashing

Product of Array Except Self

Return an array where out[i] is the product of every element of nums except nums[i], in O(n) time and without using division.

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Prefix and suffix products

prefix[i] is the product of everything left of i and suffix[i] of everything right of i. The answer for i is prefix[i] × suffix[i]: "everything except me" = "everything before me" × "everything after me".

Memory layout

Plain contiguous arrays, built with one sequential sweep each (left-to-right and right-to-left), which is ideal for hardware prefetching. Reusing the output array as the prefix removes the extra storage.

Operation	Cost
build prefix / suffix	O(n) each
combine	O(n)
extra space (output reused)	O(1) beyond the output

Running accumulator (left, right)

Instead of storing the whole suffix array, keep a single running product and fold it into the output as you sweep back.

Memory layout

Two scalar registers; the only array touched is the output.

Operation	Cost
update per element	O(1)
total	O(n) time, O(1) extra space

Why it fits

Division would be simplest (total product ÷ nums[i]), but it fails when the array contains a zero (÷ 0) and is explicitly forbidden. Prefix and suffix products avoid it.
Each position needs a product over a prefix and a suffix; both can be built incrementally (each prefix = previous prefix × one element), so the total work is linear.
Zeros need no special handling: a zero simply makes every prefix or suffix that contains it equal to 0, which is exactly the right answer.

Why alternatives degrade

Division by the total product:: Breaks with zeros (division by zero) and is disallowed by the problem statement. It also overflows more easily.
Nested loops:: O(n²) multiplications, since every position recomputes nearly the same product.
Segment tree / sparse table:: Answers range-product queries but costs O(n) to build and O(log n) per query. It is overkill when prefix and suffix are the only ranges needed.

Four approaches, from naive to production

1 · beginner

Multiply everything else, for each i

time O(n²)space O(1) beyond the output

For each position, loop over the array and multiply every element except the one at that position.

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> out;
    for (int i = 0; i < n; i++) {
        int product = 1;
        for (int j = 0; j < n; j++) {
            if (j != i) product *= nums[j];
        }
        out.push_back(product);
    }
    return out;
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] out = new int[n];
    for (int i = 0; i < n; i++) {
        int product = 1;
        for (int j = 0; j < n; j++) {
            if (j != i) product *= nums[j];
        }
        out[i] = product;
    }
    return out;
}

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    out: list[int] = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i: product *= nums[j]
        out.append(product)
    return out

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const out: number[] = [];
  for (let i = 0; i < n; i++) {
    let product = 1;
    for (let j = 0; j < n; j++) {
      if (j !== i) product *= nums[j];
    }
    out.push(product);
  }
  return out;
}

Flaws & bottlenecks

O(n²) multiplications: ~10¹⁰ for n = 10⁵.
Recomputes nearly the same product for every position; out[i] and out[i+1] differ by just two factors.
Gives no way to share work between positions.

Interviewer cross-questions

Why not compute the total product and divide?

Say: Division fails on zeros (division by zero) and the problem forbids it. You can patch it by counting zeros (0 zeros: divide; 1 zero: only that slot is non-zero; 2+ zeros: all zeros), which is the expert version, but prefix/suffix products avoid division altogether.

What is the waste here?

Say: The product to the left of i and the product to the right of i are each reused by many positions. Computing each once and combining them removes the inner loop.

Can the result overflow?

Say: Yes: products grow fast. The problem guarantees every prefix/suffix product fits a 32-bit integer. In production I would use 64-bit or checked arithmetic and state the guarantee.

2 · intermediate

Prefix array and suffix array

time O(n)space O(n)

Precompute prefix[i] (product of everything left of i) and suffix[i] (everything right of i), then multiply them position by position.

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n, 1);
    vector<int> suffix(n, 1);
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1];
    for (int i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];
    vector<int> out(n);
    for (int i = 0; i < n; i++) out[i] = prefix[i] * suffix[i];
    return out;
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n]; Arrays.fill(prefix, 1);
    int[] suffix = new int[n]; Arrays.fill(suffix, 1);
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1];
    for (int i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];
    int[] out = new int[n];
    for (int i = 0; i < n; i++) out[i] = prefix[i] * suffix[i];
    return out;
}

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n
    for i in range(1, n): prefix[i] = prefix[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1): suffix[i] = suffix[i + 1] * nums[i + 1]
    return [prefix[i] * suffix[i] for i in range(n)]

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const prefix = new Array<number>(n).fill(1);
  const suffix = new Array<number>(n).fill(1);
  for (let i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1];
  for (let i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];
  return nums.map((_, i) => prefix[i] * suffix[i]);
}

Flaws & bottlenecks

Two auxiliary arrays plus the output array: three O(n) buffers.
Three passes over memory (prefix, suffix, combine).
The extra storage is unnecessary: the suffix can be folded in as a running product.

Interviewer cross-questions

How does it handle zeros?

Say: It needs no special case. A zero anywhere makes every prefix/suffix product that spans it 0, so only the position holding the zero keeps a non-zero product (the product of everything else). That is exactly the correct answer.

Can you remove an array?

Say: Yes. Use the output array as the prefix array, then sweep right to left with a single running suffix product and multiply it in. That gives O(1) extra space: the advanced approach.

What are prefix and suffix of the first and last element?

Say: The empty product, which is 1: nothing is to the left of index 0 and nothing to the right of index n − 1. That is why both arrays start filled with 1.

3 · advanced

Output as prefix, running suffix

time O(n)space O(1) beyond the output

Write prefix products straight into the output array, then sweep right to left keeping one running product of the suffix and multiplying it into each cell.

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> out(n, 1);
    int left = 1;
    for (int i = 0; i < n; i++) {
        out[i] = left;
        left *= nums[i];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        out[i] *= right;
        right *= nums[i];
    }
    return out;
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] out = new int[n]; Arrays.fill(out, 1);
    int left = 1;
    for (int i = 0; i < n; i++) {
        out[i] = left;
        left *= nums[i];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        out[i] *= right;
        right *= nums[i];
    }
    return out;
}

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const out = new Array<number>(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) {
    out[i] = left;
    left *= nums[i];
  }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= right;
    right *= nums[i];
  }
  return out;
}

Flaws & bottlenecks

Two passes with a data dependency: each pass is sequential, so it is hard to vectorize.
The output array is used as scratch space mid-computation, so it holds a half-finished result in between.
Overflow of the running products is silent in most languages.

Interviewer cross-questions

Why does the backward pass work with a single scalar?

Say: Going right to left, at index i the running product `right` is exactly the product of everything to the right of i. out[i] already holds the product of everything to the left, so multiplying gives everything but i. Then fold nums[i] into right for the next step.

Does this count as O(1) space?

Say: The problem does not count the output array as extra space, so yes: only two scalars (left and right) are used on top of it.

How would you parallelize it?

Say: Each pass is a prefix-product scan, which parallelizes with the classic two-phase scan (per-chunk partial products, then combine chunk prefixes). The backward pass is the mirror image.

4 · expert

Zero-count fast paths

time O(n)space O(1) beyond the output

One pass counts zeros and multiplies the non-zero values. Two or more zeros mean the answer is all zeros; exactly one zero means only its own slot is non-zero. Otherwise fall back to the division-free two-pass method.

vector<int> productExceptSelf(const vector<int>& nums) {
    int n = nums.size();
    vector<int> out(n, 0);
    int zeros = 0, zeroAt = -1, product = 1;
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) { zeros++; zeroAt = i; }
        else product *= nums[i];
    }
    if (zeros > 1) return out;
    if (zeros == 1) { out[zeroAt] = product; return out; }
    int left = 1;
    for (int i = 0; i < n; i++) { out[i] = left; left *= nums[i]; }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= nums[i]; }
    return out;
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] out = new int[n];
    int zeros = 0, zeroAt = -1, product = 1;
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) { zeros++; zeroAt = i; }
        else product *= nums[i];
    }
    if (zeros > 1) return out;
    if (zeros == 1) { out[zeroAt] = product; return out; }
    int left = 1;
    for (int i = 0; i < n; i++) { out[i] = left; left *= nums[i]; }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= nums[i]; }
    return out;
}

def product_except_self(nums: Sequence[int]) -> list[int]:
    n = len(nums)
    out = [0] * n
    zeros, zero_at, product = 0, -1, 1
    for i in range(n):
        if nums[i] == 0:
            zeros += 1
            zero_at = i
        else: product *= nums[i]
    if zeros > 1: return out
    if zeros == 1:
        out[zero_at] = product
        return out
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

function productExceptSelf(nums: ArrayLike<number>): Int32Array {
  const n = nums.length;
  const out = new Int32Array(n);
  let zeros = 0, zeroAt = -1, product = 1;
  for (let i = 0; i < n; i++) {
    if (nums[i] === 0) { zeros++; zeroAt = i; }
    else product *= nums[i];
  }
  if (zeros > 1) return out;
  if (zeros === 1) { out[zeroAt] = product; return out; }
  let left = 1;
  for (let i = 0; i < n; i++) { out[i] = left; left *= nums[i]; }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) { out[i] *= right; right *= nums[i]; }
  return out;
}

Flaws & bottlenecks

More branches to test (0, 1, 2+ zeros, no zeros) for a gain that only appears when zeros are present.
The pre-scan is an extra pass in the no-zero case, so it is slightly slower than the plain two-pass version for typical data.
Still no protection against overflow beyond the 32-bit guarantee of the problem.

Interviewer cross-questions

Why are two zeros enough to stop early?

Say: Every out[i] is the product of all elements except nums[i]. With two zeros, at least one of them is always included in each product, so every out[i] is 0. You can return a zero array after a single pass, without any prefix or suffix work.

Why use Int32Array for the output?

Say: The problem guarantees 32-bit results. A typed array is one contiguous, zero-initialized, fixed-size block (no boxing, no growth, no per-element type checks), and it makes the integer width explicit.

What tests would you write?

Say: No zeros, exactly one zero (at the start, middle and end), two or more zeros, negative numbers, a length-2 array (the minimum), and values near the 32-bit limit to check the overflow assumption.

Synchronized code walkthrough

Showing: Multiply everything else, for each i — shares the player above; click any step to jump.

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> out;
    for (int i = 0; i < n; i++) {
        int product = 1;
        for (int j = 0; j < n; j++) {
            if (j != i) product *= nums[j];
        }
        out.push_back(product);
    }
    return out;
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] out = new int[n];
    for (int i = 0; i < n; i++) {
        int product = 1;
        for (int j = 0; j < n; j++) {
            if (j != i) product *= nums[j];
        }
        out[i] = product;
    }
    return out;
}

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    out: list[int] = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i: product *= nums[j]
        out.append(product)
    return out

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const out: number[] = [];
  for (let i = 0; i < n; i++) {
    let product = 1;
    for (let j = 0; j < n; j++) {
      if (j !== i) product *= nums[j];
    }
    out.push(product);
  }
  return out;
}

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n, 1);
    vector<int> suffix(n, 1);
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1];
    for (int i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];
    vector<int> out(n);
    for (int i = 0; i < n; i++) out[i] = prefix[i] * suffix[i];
    return out;
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n]; Arrays.fill(prefix, 1);
    int[] suffix = new int[n]; Arrays.fill(suffix, 1);
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1];
    for (int i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];
    int[] out = new int[n];
    for (int i = 0; i < n; i++) out[i] = prefix[i] * suffix[i];
    return out;
}

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n
    for i in range(1, n): prefix[i] = prefix[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1): suffix[i] = suffix[i + 1] * nums[i + 1]
    return [prefix[i] * suffix[i] for i in range(n)]

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const prefix = new Array<number>(n).fill(1);
  const suffix = new Array<number>(n).fill(1);
  for (let i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1];
  for (let i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];
  return nums.map((_, i) => prefix[i] * suffix[i]);
}

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> out(n, 1);
    int left = 1;
    for (int i = 0; i < n; i++) {
        out[i] = left;
        left *= nums[i];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        out[i] *= right;
        right *= nums[i];
    }
    return out;
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] out = new int[n]; Arrays.fill(out, 1);
    int left = 1;
    for (int i = 0; i < n; i++) {
        out[i] = left;
        left *= nums[i];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        out[i] *= right;
        right *= nums[i];
    }
    return out;
}

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const out = new Array<number>(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) {
    out[i] = left;
    left *= nums[i];
  }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= right;
    right *= nums[i];
  }
  return out;
}

vector<int> productExceptSelf(const vector<int>& nums) {
    int n = nums.size();
    vector<int> out(n, 0);
    int zeros = 0, zeroAt = -1, product = 1;
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) { zeros++; zeroAt = i; }
        else product *= nums[i];
    }
    if (zeros > 1) return out;
    if (zeros == 1) { out[zeroAt] = product; return out; }
    int left = 1;
    for (int i = 0; i < n; i++) { out[i] = left; left *= nums[i]; }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= nums[i]; }
    return out;
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] out = new int[n];
    int zeros = 0, zeroAt = -1, product = 1;
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) { zeros++; zeroAt = i; }
        else product *= nums[i];
    }
    if (zeros > 1) return out;
    if (zeros == 1) { out[zeroAt] = product; return out; }
    int left = 1;
    for (int i = 0; i < n; i++) { out[i] = left; left *= nums[i]; }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= nums[i]; }
    return out;
}

def product_except_self(nums: Sequence[int]) -> list[int]:
    n = len(nums)
    out = [0] * n
    zeros, zero_at, product = 0, -1, 1
    for i in range(n):
        if nums[i] == 0:
            zeros += 1
            zero_at = i
        else: product *= nums[i]
    if zeros > 1: return out
    if zeros == 1:
        out[zero_at] = product
        return out
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

function productExceptSelf(nums: ArrayLike<number>): Int32Array {
  const n = nums.length;
  const out = new Int32Array(n);
  let zeros = 0, zeroAt = -1, product = 1;
  for (let i = 0; i < n; i++) {
    if (nums[i] === 0) { zeros++; zeroAt = i; }
    else product *= nums[i];
  }
  if (zeros > 1) return out;
  if (zeros === 1) { out[zeroAt] = product; return out; }
  let left = 1;
  for (let i = 0; i < n; i++) { out[i] = left; left *= nums[i]; }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) { out[i] *= right; right *= nums[i]; }
  return out;
}