LeetCode 238: Product Of Array Except Self — Step-by-Step Visual Trace

Medium — Array | Prefix Sum | Two Pointers | Math

The Problem

Given an integer array nums, return an array where each element is the product of all elements in the original array except the element at that index. The solution must run in O(n) time without using division.

Approach

Use a two-pass algorithm to build the result array. First pass calculates left products (product of all elements to the left of each index), then second pass calculates right products and multiplies them with existing left products to get the final result.

Time: O(n) · Space: O(1)

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n

        # Calculate the left product of each element
        left_product = 1
        for i in range(n):
            result[i] *= left_product
            left_product *= nums[i]

        # Calculate the right product of each element and update the result list
        right_product = 1
        for i in range(n - 1, -1, -1):
            result[i] *= right_product
            right_product *= nums[i]

        return result

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments