DATA STRUCTURES • ALGORITHMS

Product of Array Except Self

Calculating the product of all elements in an array except the one at the current index, without using the division operator.

Time

O(N)

Space

O(1) (ignoring output)

Key Principle 1

Prefix and Suffix products

Key Principle 2

No division operator allowed

Key Principle 3

Optimal two-pass approach

Key Principle 4

Space-efficient calculation

PRODUCT_EXCEPT_SELF_LAB
ARRAY:
Current Step
Goal: Product of all except self. O(n) time, no division.
Playback
Product Tracker ⠿
STATUSInit
Two-Pass Algorithm ⠿
1res[0] = 1;
2for (int i = 1; i < n; i++) res[i] = res[i-1] * arr[i-1];
3int right = 1;
4for (int i = n-1; i >= 0; i--) { res[i] *= right; right *= arr[i]; }
1
[0]
2
[1]
3
[2]
4
[3]
?
res[0]
?
res[1]
?
res[2]
?
res[3]

Loading Lab...

Product Except Self

Product Except Self

Product of Array Except Self

Product of Array Except Self