Product of Array Except Self

PracticeNeetCode ↗LeetCode ↗

Given an integer array nums, return an array answer where answer[i] is the product of every element except nums[i] — without using division, in O(n) time.

Example

Key Pointers

• answer[i] = (product of everything left of i) × (product of everything right of i) — division isn't needed if you compute both halves directly.
• The output array can double as the prefix-product array, keeping extra space to a single running variable.
• Two linear passes (left-to-right, then right-to-left) beat any approach that rebuilds a running total per index from scratch.

Step-by-Step Analysis

1. Initialize result as an array of 1s, length n.
2. First pass (left to right): result[i] = running prefix product so far, then multiply prefix by nums[i].
3. Second pass (right to left): multiply result[i] by a running suffix product, then multiply suffix by nums[i].
4. Return result — each slot now holds prefix × suffix, i.e. the product of everything except itself.

Complexity

Time: O(n) — Space: O(1) extra, excluding the output array

Code

def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n

    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

Code Explanation

How the solution above works, piece by piece.

1. result = [1] * n: the output array doubles as storage, so no extra arrays are needed.
2. Left-to-right pass: result[i] = prefix stores the product of everything before i, then prefix *= nums[i] includes nums[i] for the next index.
3. Right-to-left pass: result[i] *= suffix multiplies in the product of everything after i, then suffix *= nums[i].
4. Each slot ends as (left product) × (right product), which is everything except nums[i], and no division was used, so zeros in the input are handled.
5. Two passes: O(n) time, O(1) extra space besides the output.

Visual Walkthrough

Running it on nums = [1, 2, 3, 4]:

Video Explanation

NeetCode — Product of Array Except Self, LeetCode 238