238. Product of Array Except Self

Medium

ArrayPrefix Sum

Companies:

AppleLinkedInAmazonFacebookMicrosoft

Answered: Apr 19, 2026

Problem Description

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.

Examples

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 <= 10⁵
-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.)

💡 Hints (2)

Solutions

Complexity Analysis

Time Complexity:

O (n^{2})

For each of the n elements, we iterate through all n elements again, resulting in $O(n^{2})$ total operations.

Space Complexity:

O (1) e x t r a s p a ce, O (n) f or t h eo u tp u t a r r a y .

No auxiliary data structures are used beyond the output array.

The brute force approach calculates the product for each index by iterating through all other elements in a nested loop. For each position i, we initialize a product of 1 and multiply every element nums[j] where j ≠ i, appending the result to the output array. While correct, this quadratic solution does not satisfy the problem's $O(n)$ requirement.

Complexity Analysis

Time Complexity:

O (n)

We make three linear passes — one to build prefix, one to build suffix, and one to compute the result — each $O(n)$ .

Space Complexity:

O (n)

Two auxiliary arrays of size n (prefix and suffix) are allocated beyond the output array.

This approach precomputes two auxiliary arrays: prefix[i] holds the product of all elements before index i, and suffix[i] holds the product of all elements after index i. We fill prefix with a forward pass and suffix with a backward pass, then combine them so that result[i] = prefix[i] * suffix[i], giving the product of all elements except the one at i.

Complexity Analysis

Time Complexity:

O (n)

Two linear passes are made over the array — one forward for prefix products and one backward for suffix products.

Space Complexity:

O (1) e x t r a s p a ce, O (n) f or t h eo u tp u t a r r a y .

Only two scalar variables (prefix and suffix) are used beyond the output array.

This solution eliminates the two auxiliary arrays from Solution 2 by writing prefix products directly into the result array. In a forward pass, result[i] is set to the running prefix product before index i. In a backward pass, a running suffix variable is multiplied into each result[i], overlaying the suffix product on top of the already-stored prefix — achieving $O(1)$ extra space.

Complexity Analysis

Time Complexity:

O (n)

A single pass of n iterations covers the entire array, with $O(1)$ work per iteration.

Space Complexity:

O (1) e x t r a s p a ce, O (n) f or t h eo u tp u t a r r a y .

Only two scalar variables (prefix and suffix) are used beyond the output array.

This solution compresses Solution 3's two passes into a single loop by simultaneously updating the result from both ends of the array. In each iteration i, the front pointer multiplies the running prefix into result[i] while the back pointer multiplies the running suffix into result[n-1-i], interleaving the prefix and suffix accumulation in one traversal.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	$O(n^{2})$	$O(1)$ extra space	Simplest to understand; no extra data structures needed	$O(n^{2})$ time fails the problem's $O(n)$ requirement
Prefix and Suffix Arrays	$O(n)$	$O(n)$	Clear, intuitive separation of prefix and suffix logic into two explicit arrays	⚠️ Requires $O(n)$ extra space for the two auxiliary arrays
Two-Pass Prefix & Suffix	$O(n)$	$O(1)$ extra space	Optimal time and space; two clean, readable passes over the array	Requires two passes instead of one
Single-Pass Prefix & Suffix	$O(n)$	$O(1)$ extra space	Same optimal complexity as Solution 3 but completes in a single loop	Interleaved bidirectional index updates reduce readability

The optimal approach for this problem is Solution 3: Two-Pass Prefix & Suffix, which achieves $O(n)$ time complexity and $O(1)$ extra space. It eliminates the auxiliary arrays of Solution 2 by writing prefix products directly into the result array and overlaying suffix products in a backward pass, satisfying both the $O(n)$ time requirement and the $O(1)$ space follow-up. Solutions marked with ⚠️ do not meet the follow-up requirement and are not recommended.

Problem Description

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.

Solutions

lines
1class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
      result = []
4
      # Loop through each element in the input list
      for i in range(len(nums)):
          product = 1
8
          # Loop through the list again to calculate the product of all elements except the current one
          for j in range(len(nums)):
              if i != j:
                  product *= nums[j]
13
          result.append(product)
15
      return result

Complexity Analysis

Time Complexity:

O (n^{2})

For each of the n elements, we iterate through all n elements again, resulting in $O(n^{2})$ total operations.

Space Complexity:

O (1) e x t r a s p a ce, O (n) f or t h eo u tp u t a r r a y .

No auxiliary data structures are used beyond the output array.

lines
1class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
      n = len(nums)
      prefix = [1] * n
      suffix = [1] * n
6
      # Calculate prefix products
      for i in range(1, n):  # Start from the second element since prefix[0] is already 1
          prefix[i] = prefix[i - 1] * nums[i - 1]
10
      # Calculate suffix products
      for i in range(n - 2, -1, -1):  # Start from the second-to-last element and go backwards
          suffix[i] = suffix[i + 1] * nums[i + 1]
14
      # Calculate the final result by multiplying prefix and suffix products
      result = []
17
      for i in range(n):
          result.append(prefix[i] * suffix[i])
20
      return result

Complexity Analysis

Time Complexity:

O (n)

We make three linear passes — one to build prefix, one to build suffix, and one to compute the result — each $O(n)$ .

Space Complexity:

O (n)

Two auxiliary arrays of size n (prefix and suffix) are allocated beyond the output array.

lines
1class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
      n = len(nums)
      result = [1] * n
5
      prefix = 1  # Initialize prefix product
7
      # Calculate the prefix product for each element
      for i in range(n):
          result[i] *= prefix
          prefix *= nums[i]
12
      suffix = 1  # Initialize suffix product
14
      # Calculate the suffix product for each element and multiply it with the prefix product
      for i in range(n - 1, -1, -1):
          result[i] *= suffix
          suffix *= nums[i]
19
      return result

Complexity Analysis

Time Complexity:

O (n)

Two linear passes are made over the array — one forward for prefix products and one backward for suffix products.

Space Complexity:

O (1) e x t r a s p a ce, O (n) f or t h eo u tp u t a r r a y .

Only two scalar variables (prefix and suffix) are used beyond the output array.

lines
1class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
      n = len(nums)
      result = [1] * n
      prefix = 1
      suffix = 1
7
      for i in range(n):
          # Update the result for the current index with the prefix product
          result[i] *= prefix
          prefix *= nums[i]
12
          # Update the result for the current index from the end with the suffix product
          result[n - 1 - i] *= suffix
          suffix *= nums[n - 1 - i]
16
      return result

Complexity Analysis

Time Complexity:

O (n)

A single pass of n iterations covers the entire array, with $O(1)$ work per iteration.

Space Complexity:

O (1) e x t r a s p a ce, O (n) f or t h eo u tp u t a r r a y .

Only two scalar variables (prefix and suffix) are used beyond the output array.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	$O(n^{2})$	$O(1)$ extra space	Simplest to understand; no extra data structures needed	$O(n^{2})$ time fails the problem's $O(n)$ requirement
Prefix and Suffix Arrays	$O(n)$	$O(n)$	Clear, intuitive separation of prefix and suffix logic into two explicit arrays	⚠️ Requires $O(n)$ extra space for the two auxiliary arrays
Two-Pass Prefix & Suffix	$O(n)$	$O(1)$ extra space	Optimal time and space; two clean, readable passes over the array	Requires two passes instead of one
Single-Pass Prefix & Suffix	$O(n)$	$O(1)$ extra space	Same optimal complexity as Solution 3 but completes in a single loop	Interleaved bidirectional index updates reduce readability

Problem Description

Examples

Example 1

Example 2

Constraints

Follow-up

💡 Hints (2)

Solutions

Solution 1: Brute Force

Complexity Analysis

Explanation

Solution 2: Prefix and Suffix Arrays

Complexity Analysis

Explanation

Solution 3: Two-Pass Prefix & Suffix

Complexity Analysis

Explanation

Solution 4: Single-Pass Prefix & Suffix

Complexity Analysis

Explanation

Conclusion

Problem Description

Examples

Example 1

Example 2

Constraints

Follow-up

💡 Hints (2)

Solutions

Solution 1: Brute Force

Complexity Analysis

Explanation

Solution 2: Prefix and Suffix Arrays

Complexity Analysis

Explanation

Solution 3: Two-Pass Prefix & Suffix

Complexity Analysis

Explanation

Solution 4: Single-Pass Prefix & Suffix

Complexity Analysis

Explanation

Conclusion