Suffix Sum — Product of Array Except Self

Before we start

You just learned that a prefix precomputes from the left. This chapter adds the mirror image: precompute from the right — and then shows what happens when you combine the two. By the end you will be able to:

• See the left-pass / right-pass two-pass framework as one mental picture.
• Explain why the no-division product trick is equivalent to division, but safer.
• Recognise problems that need information from both sides of a position simultaneously.

Stop at every Pause & Think box. The insight there is what separates people who memorise this solution from people who understand it.

Picture this first (no code yet)

[flour, eggs, sugar, butter, vanilla, salt]

That two-pass assembly line is the pattern. Let's now see it solve a real problem.

The actual problem

Given an integer array nums, return an array output such that output[i] is the product of all elements except nums[i]. Do it in O(n) time, O(1) extra space (not counting the output), and without division.

nums   = [1,  2,  3,  4]
output = [24, 12,  8,  6]
  because:
    output[0] = 2×3×4 = 24
    output[1] = 1×3×4 = 12
    output[2] = 1×2×4 = 8
    output[3] = 1×2×3 = 6

The "no division" constraint rules out the obvious shortcut (total product ÷ nums[i]). More importantly, division breaks when any element is 0. The two-pass approach handles zeros naturally.

First, the slow way (so you feel the pain)

def product_except_self_slow(nums):
    n = len(nums)
    output = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        output.append(product)
    return output

For each of the n positions, you multiply the remaining n-1 elements — O(n) work per position, O(n²) total.

n = 10        →  ~100 multiplications
n = 10,000    →  ~100,000,000 multiplications
n = 100,000   →  ~10,000,000,000 multiplications  (ten billion — painful)

The turning point

You'd compute a suffix product: suffix[i] = product of nums[i+1] through nums[n-1]. Then:

output[i] = prefix_product[i-1] × suffix_product[i+1]
          = (everything to the left) × (everything to the right)

That's the whole algorithm. Two passes, no division.

The one idea to remember

Watch it happen, frame by frame

nums = [1, 2, 3, 4]

Left pass — fill output[i] with the product of everything LEFT of i:

i=0:  nothing to the left  →  output[0] = 1
i=1:  nums[0]              →  output[1] = 1
i=2:  nums[0]×nums[1]      →  output[2] = 1×2 = 2
i=3:  nums[0]×nums[1]×nums[2]  →  output[3] = 1×2×3 = 6

output after left pass: [1, 1, 2, 6]

Right pass — multiply each output[i] by the product of everything RIGHT of i:

We track a running right variable (starts at 1) as we scan from right to left.

i=3:  nothing to the right →  output[3] = 6 × 1 = 6.   right = right × nums[3] = 1×4 = 4
i=2:  right = 4            →  output[2] = 2 × 4 = 8.   right = 4×3 = 12
i=1:  right = 12           →  output[1] = 1 × 12 = 12.  right = 12×2 = 24
i=0:  right = 24           →  output[0] = 1 × 24 = 24.  right = 24×1 = 24

output after right pass: [24, 12, 8, 6]  ✅

i=0: output[0] = 1
i=1: output[1] = 2
i=2: output[2] = 2×3 = 6
i=3: output[3] = 2×3×4 = 24

output = [1, 2, 6, 24]

i=3: output[3] = 24×1 = 24,  right = 5
i=2: output[2] = 6×5 = 30,   right = 5×4 = 20
i=1: output[1] = 2×20 = 40,  right = 20×3 = 60
i=0: output[0] = 1×60 = 60,  right = 60×2 = 120

output = [60, 40, 30, 24]  ✅

Now, the code — line by line

def productExceptSelf(nums):
    n = len(nums)
    output = [1] * n           # initialise with 1s — multiplication's identity

    # Left pass: output[i] = product of all elements to the LEFT of i
    left = 1
    for i in range(n):
        output[i] = left           # nothing to the left of i yet (left accumulates BEFORE update)
        left *= nums[i]            # update left to include nums[i] for the NEXT position

    # Right pass: multiply output[i] by product of all elements to the RIGHT of i
    right = 1
    for i in range(n - 1, -1, -1):
        output[i] *= right         # fold in the right-side product
        right *= nums[i]           # update right to include nums[i] for the NEXT (leftward) position

    return output

Mapping to the bakery:

• output[i] = left — "Write down how much was multiplied on my left so far."
• left *= nums[i] — "Include this ingredient in the left product for the next station."
• output[i] *= right — "Fold in how much was multiplied on my right so far."
• right *= nums[i] — "Include this ingredient in the right product for the next (leftward) station."

Why O(1) extra space? We use only two integer variables (left, right). The output array itself doesn't count toward "extra" space — it's the required return value.

Why does it never go wrong?

For any index i, after both passes:

output[i]
  = (product of nums[0..i-1])         ← set in the left pass
  × (product of nums[i+1..n-1])       ← multiplied in the right pass
  = product of everything except nums[i]

nums[i] is never included because:

• The left variable at position i holds the product of 0..i-1 (updated after recording output[i]).
• The right variable at position i holds the product of i+1..n-1 (updated after multiplying into output[i]).

The "update after use" ordering is the key — and it's deliberate.

Why is it so fast?

The deeper idea — the two-pass framework

Prefix sum and suffix sum are the same concept at different scales:

The two-pass framework applies whenever:

• You need something from the left AND something from the right of each position simultaneously.
• You can't just loop twice naively (that's O(n²)).
• A single left-to-right pass followed by a single right-to-left pass gives you both pieces in O(n).

This framework shows up in: trapping rain water (prefix-max + suffix-max), minimum domino rotations, jump game variants, and many more.

When should I reach for this? (the trigger list)

Reach for the two-pass / suffix pattern when you notice:

• Each position's answer depends on elements to its left AND elements to its right.
• The naive approach would be O(n²) because of nested loops.
• The words "except itself," "all others," or "neighbours" appear.
• You've already used a left pass and realise you still need the right side — that's the signal.
• The problem explicitly says no division (your first instinct might be prefix product ÷ self — block it).

The same trick in three disguises

Disguise 1 — Trapping Rain Water (revisited differently)

Water trapped at position i = min(max_left, max_right) - height[i].

• Left pass: For each i, record the maximum height seen so far from the left.
• Right pass: For each i, record the maximum height seen so far from the right.
• Combine: water[i] = min(left_max[i], right_max[i]) - height[i].

Same left-pass / right-pass / combine skeleton. Different operation (max instead of product).

Disguise 2 — Sum of Subarray Minimums (LC #907)

For each element, find the "span" of subarrays for which it is the minimum — done with a left pass (previous smaller element) and a right pass (next smaller element). Two-pass framework with monotonic stacks.

Disguise 3 — Candy (LC #135)

Assign minimum candies to children based on rating comparisons with neighbours:

• Left pass: Assign candies based on "is my rating higher than my left neighbour?"
• Right pass: Adjust candies based on "is my rating higher than my right neighbour?"
• Combine: max(left_candy[i], right_candy[i]).

Identical skeleton — left pass, right pass, combine with an element-wise operation.

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll use two passes. First, a left-to-right pass where I store the product of all elements to the left of each index. Then, a right-to-left pass where I multiply in the product of all elements to the right. Each index ends up with the product of everything except itself — O(n) time and O(1) extra space, with no division."

Check yourself

Practice problems

Next up: Kadane's Algorithm, where we discover that you only need to remember one number — the best sum ending at the current position — to find the maximum subarray in a single pass.