Product of Array Except Self

mediumTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(1)
Arrays & HashingOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Compute prefix products left-to-right directly into `res[i]`, then sweep right-to-left maintaining a running scalar `suffix` product and multiply `res[i] *= suffix`.

2. Complexity Bounds & Proof

Two linear passes reuse the output array for prefix storage and a single scalar for suffix products, achieving O(1) extra space without division.

3. Minimal Idiomatic Code

def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [1] * n
    prefix = 1
    for i in range(n):
        res[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= suffix
        suffix *= nums[i]
    return res

4. Failure Modes & Interview Follow-ups

Pitfalls:- Using total product divided by `nums[i]` crashes on zeros and violates the division constraint.
Follow-ups:- Counting zeros fixes division only if division were allowed; prefix-suffix works uniformly in rings without division.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Maximum Product Subarray (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.