Leetcode - 238. Product of Array Except Self

Medium

Dec 22, 2025

#math

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Notes

Intuition

The product of all elements except self is equivalent to (product of all elements before i) × (product of all elements after i). We can precompute these prefix and suffix products.

Implementation

Build a prefix array where prefix[i] is the product of all elements before index i. Initialize prefix[0] = 1 (nothing before it), then prefix[i] = nums[i-1] * prefix[i-1]. Similarly, build a suffix array from right to left where suffix[i] is the product of all elements after index i. The answer at each index is prefix[i] * suffix[i].

Edge-cases

The edge indices are handled by initializing prefix and suffix with 1s. No division is needed, so zeros in the array don't cause issues.

Time: O(n) — three linear passes
Space: O(n) — prefix and suffix arrays (can be optimized to O(1) by computing on the fly)

Complexity

Solution

from typing import List

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

        prefix = [1] * n
        for i in range(1, n):
            prefix[i] = nums[i - 1] * prefix[i - 1]

        suffix = [1] * n
        for i in range(n - 2, -1, -1):
            suffix[i] = nums[i + 1] * suffix[i + 1]

        ans = [1] * n
        for i in range(n):
            ans[i] = prefix[i] * suffix[i]
        return ans
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()