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

Product of Array Except Self – Solution & Complexity

Interview solutions
/
Product of Array Except Self

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
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?