Product Except Self — The Factory Line

Boss 6, a curveball

This one's a little different. It's in the Arrays & Hashing dungeon, but the weapon isn't a hash map. It's a technique called prefix and suffix arrays which is pure array work. No hashing at all.

Why put it here? Because this pattern shows up in dozens of other problems across later dungeons, and learning it early makes those future bosses easier. Think of it as a side quest.

The story

You're a shift manager at a factory. The factory makes... something. Doesn't matter. There's a conveyor belt and a row of stations. Each station has a number on it. When a product moves down the belt, each station multiplies the running product by its number.

So if the stations are [2, 3, 4, 5, 6], a single product going end to end gets multiplied by 2, then 3, then 4, then 5, then 6. Final number: 720.

Easy.

Then the big boss walks in holding a clipboard. "I'm doing a performance review. For each station, I want to know what the final product would have been if that station had been skipped today. Every station. By end of shift."

You pull out the list of station values: [2, 3, 4, 5, 6].

• If station 0 (the 2) had been skipped: 3 × 4 × 5 × 6 = 360
• If station 1 (the 3) had been skipped: 2 × 4 × 5 × 6 = 240
• If station 2 (the 4) had been skipped: 2 × 3 × 5 × 6 = 180
• If station 3 (the 5) had been skipped: 2 × 3 × 4 × 6 = 144
• If station 4 (the 6) had been skipped: 2 × 3 × 4 × 5 = 120

You need to hand back [360, 240, 180, 144, 120].

With five stations it's a 5-minute job. The boss mentions there are actually 600 stations and she wants it in 20 minutes.

The naive way

For each station, multiply all the others.

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

That's the nested loop again. O(n²). For 600 stations, 360,000 multiplications. Doable but ugly and it won't pass interview constraints.

The "cheat" way (division)

A tempting idea. Compute the full product once. Then for each station, divide by that station's value.

def product_except_self_division(nums):
    total = 1
    for x in nums:
        total *= x
    return [total // x for x in nums]

This is O(n). And it's wrong as soon as any station has a zero. Division by zero blows up. Even if there's no zero, interviewers explicitly forbid this approach because they want you to solve it without division. Real-world floating-point issues make this flaky anyway.

The weapon: prefix and suffix

Here's the insight. For any station i, the answer is:

(product of everything to the left of i)  ×  (product of everything to the right of i)

That's it. If you had those two numbers available for each station, the answer is just one multiplication.

So the plan:

1. Walk left to right. At each index, compute the product of everything before it. Call this the prefix product.
2. Walk right to left. At each index, compute the product of everything after it. Call this the suffix product.
3. Multiply prefix and suffix at each index. That's the answer.

Each walk is O(n). You do two of them. Total: O(n). No division.

Let me walk the prefix calculation on [2, 3, 4, 5, 6]:

Prefix is [1, 2, 6, 24, 120]. Note how index 0 gets 1, the identity for multiplication, because there's nothing to the left.

Suffix is symmetric:

Suffix is [360, 120, 30, 6, 1].

Now multiply element by element:

[1×360, 2×120, 6×30, 24×6, 120×1] → [360, 240, 180, 144, 120] ✓

The code

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n
 
    # First pass: result[i] becomes the prefix product
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
 
    # Second pass: multiply in the suffix product
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
 
    return result

Read it slow. First pass fills result[i] with the product of everything before index i. Second pass multiplies into result[i] the product of everything after. You never store a separate prefix and suffix array. You reuse result for both. The extra space is O(1), not counting the output.

Complexity

Prefix/suffix is the best of all worlds. Linear time, constant extra space, and no division tricks.

Gotchas

1. Initializing prefix or suffix to 0. Should be 1. The identity for multiplication is 1. If you start at 0, everything stays 0 and you're back to debugging.

2. Order of result[i] = prefix and prefix *= nums[i]. As noted above. The "current index's value" must not be included in the prefix at the current index. Assign first, multiply second.

3. Counting the output array as extra space. The problem usually says "O(1) extra space, excluding the output". The output array is mandatory and doesn't count. Read carefully.

4. Two-array version. It's fine to write the first version with an explicit prefix[] and suffix[] array for clarity. Then optimize into the single-array version once you're confident. Interviewers usually accept either, but they smile at the single-array one.

What you really learned

Prefix and suffix arrays are one of the most reusable techniques in array problems. The core idea is: precompute some aggregate from the left (or right) so that when you need information about "everything before this index" or "everything after", you can look it up in O(1).

You'll see this everywhere:

• Range sum queries: "what's the sum from index i to j?". Precompute a prefix sum array, then prefix[j] - prefix[i] answers in O(1).
• Best time to buy and sell stock: precompute min-so-far to the left of each index, profit at each index is price[i] - min_so_far.
• Trapping rain water: precompute max-height to the left and right, water at index i is min(left, right) - height[i].
• This problem: precompute prefix and suffix products.

Whenever you're computing something over "everything before" or "everything after" an index, think prefix or suffix arrays.

Boss down

600 stations. Boss's answer ready in 15 minutes, ahead of schedule. You get pizza at the staff meeting.

Next up: Boss 7 — The Yearbook Chain. The diner's alumni binder has graduation years for everyone who ever worked there, but they're out of order and some years have nobody. You'll find the longest consecutive streak of years without doing any sorting. It's the final boss of Dungeon 1 and it's a beautiful twist on the hash set you met back in Boss 1.

Bring a pen and a nostalgic mood. See you at the yearbook.