Sign in
Skip to solution
mediumDSA

How do you compute the product of an array except self without division?

467 views
01

Understand the problem

Explain product-except-self.

arraysprefix-product
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Build a prefix product (product of everything to the left) and a suffix product (everything to the right); the answer for index i is prefix[i] * suffix[i]. Do it in two passes, reusing the output array, for O(n) time and O(1) extra space. Division is disallowed because of zeros.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Prefix then suffix
Run Playground
def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    prefix = 1
    for i in range(n):
        out[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        out[i] *= suffix
        suffix *= nums[i]
    return out


# --- demo ---
print(product_except_self([1, 2, 3, 4]))   # [24, 12, 8, 6]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 73 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track