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)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

• 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'. The nested loops cause 
        # the number of operations to grow quadratically.
        # Space Complexity: O(N) or O(1) auxiliary space, as 'result_list' is used to store 
        # the output and we don't use any other extra space.
        
        result_list = []
        for index, num in enumerate(nums):
            product_result = 1
            for s_index, s_num in enumerate(nums):
                # Skip the current index to calculate the product of the REST of the elements
                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

結語：

前綴與後綴積 (Prefix and Suffix Products) 與 預先分配 (Pre-allocation)

將原問題拆解為：「左側所有數字的乘積」乘以「右側所有數字的乘積」。

分別由左至右、由右至左各掃描陣列一次，就能避開重複計算，將時間複雜度降至 O(N)。

這是一種經典的「以空間換取時間」，並利用兩次單向掃描來取代嵌套迴圈的演算法模式。