LeetCode 238 - Products of Array Except Self

2026-04-08

medium　array

Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].Each product is guaranteed to fit in a 32-bit integer.Follow-up: Could you solve it in O(n) time without using the division operation?

Example 1:

Input: nums = [1,2,4,6]

Output: [48,24,12,8]

Example 2:

Input: nums = [-1,0,1,2,3]

Output: [0,-6,0,0,0]

Constraints:

• 2 <= nums.length <= 1000
• -20 <= nums[i] <= 20

Solution 1:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # Brute-force Approach.
        # For each element in the array, we calculate the product of all other elements.
        # We achieve this by using nested loops: the outer loop selects the current element to exclude,
        # and the inner loop multiplies all the other elements together.

        # Time Complexity: O(N^2), where N is the length of 'nums'.
        # Space Complexity: O(N) or O(1) auxiliary space, as 'result_list' stores the output only.

        result_list = []
        for index, num in enumerate(nums):
            product_result = 1
            for s_index, s_num in enumerate(nums):
                if index == s_index:
                    continue
                product_result *= s_num
            result_list.append(product_result)

        return result_list

Solution 2:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        """
        Calculates the product of all elements in the array except self.

        This algorithm uses the prefix and suffix product technique to achieve O(N)
        time complexity without utilizing the division operation.

        Time Complexity: O(N), where N is the length of nums.
        Space Complexity: O(N), for storing the prefix and suffix product arrays.
        """
        n = len(nums)

        # Pre-allocate arrays to optimize memory allocation and avoid O(N) insertion costs
        left_list = [1] * n
        right_list = [1] * n
        result_list = [1] * n

        # Compute prefix products: product of all elements to the left of index 'i'
        for i in range(1, n):
            left_list[i] = left_list[i - 1] * nums[i - 1]

        # Compute suffix products: product of all elements to the right of index 'i'
        for i in range(n - 2, -1, -1):
            right_list[i] = right_list[i + 1] * nums[i + 1]

        # Combine prefix and suffix products to form the final result
        for i in range(n):
            result_list[i] = left_list[i] * right_list[i]

        return result_list

Takeaway

Prefix and Suffix Products & Pre-allocation

Break the problem into two sub-problems: the product of all elements to the left of index i, multiplied by the product of all elements to the right of index i.

By scanning the array once left-to-right and once right-to-left, we eliminate redundant computation and achieve O(N) time complexity.

This is a classic space-for-time tradeoff — replacing nested loops with two single-pass scans over the array.