[LeetCode] 238. Product of Array Except Self

🧠 Remember: “Everyone except me = left × right.”

The problem — 20 seconds

nums = [1, 2, 3, 4] → [24, 12, 8, 6].

For each index, return the product of everything except that element. No division, O(n) time — and as a follow-up, O(1) extra space.

Original on LeetCode

a    = [1,  2,  3, 4]
LEFT = [1,  1,  2, 6]    ← product of everything before i
RIGHT= [24, 12, 4, 1]    ← product of everything after i
ans  = [24, 12, 8, 6]    ← LEFT[i] × RIGHT[i]

That is the whole algorithm. Everything below just makes it obvious why.

Your first instinct

Divide the total product by each element:

total = 1
for x in nums:
    total *= x
return [total // x for x in nums]

Two problems. First, the problem bans division outright. Second, a single zero nukes the scheme: total becomes 0, yet the true answer for [0, 1, 2] is [2, 0, 0]. Division can’t tell which positions deserve the non-zero value.

The turning point

Stop thinking about what to remove — think about what remains: a left part and a right part, each a running product built in one sweep.

Walk left → right accumulating L. Walk right → left accumulating R. Multiply pointwise. Two linear passes, zero division, zeroes handled for free.

Watch it work

Press Play: LEFT fills left → right, RIGHT fills right → left, then each L[i] × R[i] lands. The last step covers the zero case and the O(1) fold.

Interactive visual · Left × Right

Everyone except me = left × right

For each position, everything else splits into two groups: what's left of me and what's right of me. Build a running product from each side, then multiply the two. Press Play and watch [1, 2, 3, 4] become [24, 12, 8, 6].

nums a

LEFT products L — product of everything before i

RIGHT products R — product of everything after i

answer ans[i] = L[i] × R[i]

Step 1 / 1 Speed

1L[0] = 1; for i in 1..n-1: L[i] = L[i-1] * a[i-1]

2R[n-1] = 1; for i in n-2..0: R[i] = R[i+1] * a[i+1]

3ans[i] = L[i] * R[i] # O(1) variant: fold R into ans

Quick check — make it stick

Why no division?

🧠 Memory hook: “Everyone except me = left × right.” The answer at each spot is just the product of everything before it times everything after it.

What the code is really saying

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans: List[int] = [1] * n
        for i in range(1, n):          # LEFT sweep, stored in ans
            ans[i] = ans[i - 1] * nums[i - 1]
        right = 1                      # RIGHT sweep folded into one variable
        for i in range(n - 1, -1, -1):
            ans[i] *= right
            right *= nums[i]
        return ans

Read it as the visual: the first loop paints LEFT into ans, the second multiplies in RIGHT on the fly — no second array, just the running right.

One trap: seed with 1, not 0. The empty product — nothing left of index 0 — is the multiplicative identity. Seed with 0 and every answer collapses.

Why it works

Invariant: after the forward pass, ans[i] holds everything strictly before i; the backward pass multiplies in everything strictly after. Each slot ends as left × right — everything except itself, by definition.

Two linear sweeps, one output array + one variable: time O(n), space O(1) extra.

🧠 Remember

Product Except Self → “Everyone except me = left × right.” When division is banned, split the world at i and accumulate from both sides.

🔁 Try this: what changes with two zeroes in the input? (Hint: every answer is zero — can you see why?) Then try Maximum Product Subarray — same prefix instinct, sign flips included.