DSA Tracker

Visualize

Product of Array Except Self

Prefix × suffix passes — no division

time O(n)space O(1) extra

Dividing the total product by nums[i] breaks on zeros and is usually banned anyway. The clean decomposition: out[i] = (product of everything LEFT of i) × (product of everything RIGHT of i). Two linear passes fill both factors — first a running prefix sweeps left to right writing into out, then a running suffix sweeps right to left multiplying itself in. The displayed row IS the output array as it fills.

Details

Animated on: For nums = [1,2,3,4,5], build out where out[i] is the product of every element EXCEPT nums[i]. Division is off the table.

Problem:Product of Array Except SelfMedium

Prefix × suffix passes — no division

step 1 / 13

?
[0]
?
[1]
?
[2]
?
[3]
?
[4]

out starts empty and L carries 'product of all cells left of i', seeded 1. Pass 1 writes only left-products; pass 2 will multiply in the right side.

  • i=0· arr[0] = ?
Pseudocode
1FUNCTION productExceptSelf(nums):
2  n = the length of nums; out = an empty array of size n; L = 1   (L = product of everything to the left)
3  FOR i from 0 to n-1:
4    set out[i] to L; then multiply L by nums[i]
5  R = 1   (R = product of everything to the right)
6  FOR i from n-1 down to 0:
7    multiply out[i] by R; then multiply R by nums[i]
8  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. out starts empty and L carries 'product of all cells left of i', seeded 1. Pass 1 writes only left-products; pass 2 will multiply in the right side.
  2. Nothing sits left of index 0, so its left-product is the empty product 1. Then L consumes nums[0]=1: L = 1·1 = 1.
  3. Left of index 1 lies only {1}, so out[1] = 1. L absorbs nums[1]=2 → L = 2.
  4. Left of index 2 is {1,2} → out[2] = 2. L grows to 2·nums[2] = 6.
  5. Left of index 3 is {1,2,3} → out[3] = 6. L becomes 6·4 = 24.
  6. out[4] = 24 = 1·2·3·4 — every cell now holds its LEFT-neighbour product only. Halfway there: each still misses everything to its right.
  7. Pass 2 sweeps the other direction with R = 'product of all cells right of i', seeded 1. Starting at index 4.
  8. Index 4 has nothing to its right: out[4] = 24 × 1 stays 24. R absorbs nums[4]=5 → R = 5.
  9. out[3] = 6 × 5 = 30 — the left-product {1,2,3} times the right-product {5}. Check: 1·2·3·5 = 30. R becomes 5·4 = 20.
  10. out[2] = 2 × 20 = 40 — left {1,2} times right {4,5}: 1·2·4·5 = 40. R grows by nums[2]=3 → 60.
  11. out[1] = 1 × 60 = 60 — left {1} times right {3,4,5}: 1·3·4·5 = 60. R absorbs nums[1]=2 → 120.
  12. Last cell: out[0] = 1 × 120 = 120 = 2·3·4·5 — everything except nums[0]. Both passes complete.
  13. Answer: [120, 60, 40, 30, 24]. Each entry = prefix × suffix with zero divisions — two O(n) passes and one rolling scalar per direction.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Product of Array Except Self in the editorAll Arrays problemsBack to roadmap