{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Product of Array Except Self – Solution & Complexity

Interview solutions
/
Product of Array Except Self

Watch: Product of Array Except Self with prefix and suffix products

Every answer is the product of everything to its left times everything to its right. One pass left to right writes the running prefix product into the output before folding in the current number; a second pass right to left multiplies in the running suffix product. O(n) time, O(1) extra space, no division, and zeros need no special case.

Solution Walkthrough

  1. Step 1: Understand Each Output Position

    • For each index i, the answer should be the product of every number except nums[i].
    • Division is not allowed, so we cannot compute one total product and divide by the current value.
    • The output order must match the input order exactly.

  2. Step 2: Consider the Brute Force Idea

    • For each index, multiply all values at every other index.
    • This is correct and handles zeroes, but it repeats almost the same multiplication for every position.
    • The nested loops make the time complexity O(n²).
    def product_except_self(nums: list[int]) -> list[int]:
    answer = []
    for i in range(len(nums)):
        product = 1
        for j in range(len(nums)):
            if i != j:
                product *= nums[j]
        answer.append(product)
    return answer

  3. Step 3: Split the Product into Left and Right Parts

    • The product except self is the product of everything to the left times everything to the right.
    • A prefix pass can store products before each index.
    • A suffix pass can multiply in products after each index.

  4. Step 4: Fill Prefix Products First

    • Start with an answer array filled with 1.
    • Move left to right while carrying a running prefix product.
    • Before multiplying by nums[i], store the product of all values to the left in answer[i].
    def product_except_self(nums: list[int]) -> list[int]:
    answer = [1] * len(nums)
    prefix = 1
    for i in range(len(nums)):
        answer[i] = prefix
        prefix *= nums[i]
    return answer

  5. Step 5: Final Solution and Complexity

    • The second pass moves right to left with a running suffix product.
    • Multiplying answer[i] by the suffix gives left product times right product, excluding nums[i] itself.
    • Time complexity is O(n), and extra space is O(1) besides the required output array.
    def product_except_self(nums: list[int]) -> list[int]:
    answer = [1] * len(nums)

    prefix = 1
    for i in range(len(nums)):
        answer[i] = prefix
        prefix *= nums[i]

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

    return answer
Learn the Arrays & Hashing pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Product of Array Except Self online (run code in the browser)Subarray Sum Equals K solution (medium)3Sum solution (medium)3Sum Closest solution (medium)Best Time to Buy and Sell Stock solution (easy)All coding interview problems