LeetCode 238 - Product of Array Except Self

The problem gives an integer array nums, and for every index i, we must compute the product of every element in the array except nums[i].

leetcodemediumarrayprefix-sum

LeetCode Problem 238

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem gives an integer array nums, and for every index i, we must compute the product of every element in the array except nums[i].

If the input is:

nums = [1,2,3,4]

then:

  • For index 0, we multiply 2 * 3 * 4 = 24
  • For index 1, we multiply 1 * 3 * 4 = 12
  • For index 2, we multiply 1 * 2 * 4 = 8
  • For index 3, we multiply 1 * 2 * 3 = 6

So the result becomes:

[24,12,8,6]

The important restriction is that we are not allowed to use division. A simple idea might be:

  1. Compute the product of all numbers
  2. Divide by nums[i]

However, division is explicitly forbidden. Even if division were allowed, zeros would make that approach tricky because division by zero is undefined.

The constraints tell us several important things:

  • nums.length can be as large as 10^5
  • Therefore, any O(n^2) solution will likely be too slow
  • We need an O(n) algorithm
  • The product of prefixes and suffixes fits in a 32-bit integer, so overflow is not a concern in the intended solutions

The follow up asks whether we can solve the problem with O(1) extra space, excluding the output array itself. This strongly hints that we should reuse the output array instead of creating multiple helper arrays.

Several edge cases are especially important:

  • Arrays containing zero
  • Arrays containing multiple zeros
  • Negative numbers
  • Very small arrays such as length 2

A naive implementation often fails on zero handling, especially if it relies on division.

Approaches

Brute Force Approach

The most direct solution is to compute the answer for each index independently.

For every position i:

  1. Initialize a product variable to 1
  2. Iterate through the entire array
  3. Multiply every element except nums[i]
  4. Store the result

This works because we explicitly compute exactly what the problem asks for. However, for each element we scan the entire array again.

If the array has n elements:

  • We perform n passes
  • Each pass costs O(n)
  • Total complexity becomes O(n^2)

With n up to 100000, this approach is too slow.

Optimal Prefix and Suffix Product Approach

The key insight is that for every index i, the answer can be split into two independent parts:

product of elements to the left of i
*
product of elements to the right of i

For example:

nums = [1,2,3,4]

For index 2:

left product  = 1 * 2 = 2
right product = 4
answer        = 2 * 4 = 8

Instead of recomputing these products repeatedly, we can build them incrementally.

We first compute prefix products:

prefix[i] = product of all elements before i

Then compute suffix products:

suffix[i] = product of all elements after i

Finally:

answer[i] = prefix[i] * suffix[i]

We can optimize space further by storing prefix products directly inside the output array, then multiplying by suffix products during a backward pass.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Recomputes products for every index
Optimal O(n) O(1) extra space Uses prefix and suffix products efficiently

Algorithm Walkthrough

  1. Create an output array answer of size n, initialized with 1.

We will use this array to store prefix products first, then update it with suffix products later. 2. Traverse the array from left to right while maintaining a running prefix product.

At each index i:

  • answer[i] should contain the product of all elements before i
  • Then update the running prefix product by multiplying with nums[i]

Example:

nums = [1,2,3,4]

Prefix pass:

answer = [1,1,2,6]
  1. Traverse the array from right to left while maintaining a running suffix product.

At each index i:

  • Multiply answer[i] by the current suffix product
  • Update the suffix product by multiplying with nums[i]

This adds the contribution of all elements to the right of i. 4. Return the final answer array.

After the backward pass, every position contains:

product of left elements * product of right elements

Why it works

During the first pass, answer[i] stores the product of all elements strictly to the left of index i.

During the second pass, the suffix variable stores the product of all elements strictly to the right of index i.

Multiplying these two values together gives exactly the product of every element except nums[i].

Because every element contributes either to the left product or the right product, and never both, the result is correct for every index.

Python Solution

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        
        answer = [1] * n
        
        prefix_product = 1
        for i in range(n):
            answer[i] = prefix_product
            prefix_product *= nums[i]
        
        suffix_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix_product
            suffix_product *= nums[i]
        
        return answer

The implementation uses two passes over the array.

The first loop computes prefix products. Before multiplying by nums[i], the current prefix_product represents the product of all values to the left of i. That value is stored directly into answer[i].

After storing it, we extend the prefix by multiplying with the current element.

The second loop moves backward through the array. At every step, suffix_product contains the product of all elements to the right of the current index.

We multiply the existing prefix value in answer[i] by this suffix product. This combines the left and right contributions into the final answer.

Because the output array itself is reused, we avoid allocating separate prefix and suffix arrays.

Go Solution

func productExceptSelf(nums []int) []int {
	n := len(nums)

	answer := make([]int, n)

	for i := 0; i < n; i++ {
		answer[i] = 1
	}

	prefixProduct := 1
	for i := 0; i < n; i++ {
		answer[i] = prefixProduct
		prefixProduct *= nums[i]
	}

	suffixProduct := 1
	for i := n - 1; i >= 0; i-- {
		answer[i] *= suffixProduct
		suffixProduct *= nums[i]
	}

	return answer
}

The Go implementation follows the exact same logic as the Python version.

A slice is created using make([]int, n), and each position is initialized to 1.

Go slices behave similarly to dynamic arrays, so we can update values in place efficiently.

Integer overflow is not a concern because the problem guarantees the results fit within 32-bit integers.

Unlike Python, Go does not automatically initialize slices with 1, so we explicitly fill the array before starting the prefix computation.

Worked Examples

Example 1

nums = [1,2,3,4]

Prefix Pass

i nums[i] prefix_product before update answer
0 1 1 [1,1,1,1]
1 2 1 [1,1,1,1]
2 3 2 [1,1,2,1]
3 4 6 [1,1,2,6]

After prefix pass:

answer = [1,1,2,6]

Suffix Pass

i nums[i] suffix_product before update answer
3 4 1 [1,1,2,6]
2 3 4 [1,1,8,6]
1 2 12 [1,12,8,6]
0 1 24 [24,12,8,6]

Final result:

[24,12,8,6]

Example 2

nums = [-1,1,0,-3,3]

Prefix Pass

i nums[i] prefix_product before update answer
0 -1 1 [1,1,1,1,1]
1 1 -1 [1,-1,1,1,1]
2 0 -1 [1,-1,-1,1,1]
3 -3 0 [1,-1,-1,0,1]
4 3 0 [1,-1,-1,0,0]

After prefix pass:

answer = [1,-1,-1,0,0]

Suffix Pass

i nums[i] suffix_product before update answer
4 3 1 [1,-1,-1,0,0]
3 -3 3 [1,-1,-1,0,0]
2 0 -9 [1,-1,9,0,0]
1 1 0 [1,0,9,0,0]
0 -1 0 [0,0,9,0,0]

Final result:

[0,0,9,0,0]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Two linear passes through the array
Space O(1) extra space Only a few variables are used besides the output array

The algorithm processes the array twice, once from left to right and once from right to left. Each pass touches every element exactly once, so the total runtime is linear.

The only extra variables used are the prefix and suffix accumulators. Since the output array does not count toward extra space according to the problem statement, the solution satisfies the O(1) extra space requirement.

Test Cases

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        
        answer = [1] * n
        
        prefix_product = 1
        for i in range(n):
            answer[i] = prefix_product
            prefix_product *= nums[i]
        
        suffix_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix_product
            suffix_product *= nums[i]
        
        return answer

solution = Solution()

assert solution.productExceptSelf([1,2,3,4]) == [24,12,8,6]  # basic positive numbers

assert solution.productExceptSelf([-1,1,0,-3,3]) == [0,0,9,0,0]  # single zero case

assert solution.productExceptSelf([0,0]) == [0,0]  # multiple zeros

assert solution.productExceptSelf([2,3]) == [3,2]  # minimum array length

assert solution.productExceptSelf([-1,-2,-3,-4]) == [-24,-12,-8,-6]  # all negatives

assert solution.productExceptSelf([1,1,1,1]) == [1,1,1,1]  # all ones

assert solution.productExceptSelf([5]) if False else True  # invalid by constraints

assert solution.productExceptSelf([10,0,5]) == [0,50,0]  # zero in middle

assert solution.productExceptSelf([3,4,5,6]) == [120,90,72,60]  # larger products

assert solution.productExceptSelf([-2,3,-4]) == [-12,8,-6]  # mixed signs
Test Why
[1,2,3,4] Standard example with positive integers
[-1,1,0,-3,3] Tests handling of a single zero
[0,0] Ensures multiple zeros produce all zeros
[2,3] Smallest valid input size
[-1,-2,-3,-4] Validates negative number handling
[1,1,1,1] Checks repeated neutral elements
[10,0,5] Verifies correct zero propagation
[3,4,5,6] Tests normal multi-element multiplication
[-2,3,-4] Mixed positive and negative values

Edge Cases

One important edge case is when the array contains exactly one zero. In this situation, every position except the zero's position must become 0, because every product includes that zero. The position containing the zero should equal the product of all non-zero elements. Division-based approaches often fail here, but the prefix-suffix method handles it naturally because the zero simply propagates through prefix and suffix products.

Another critical edge case is when the array contains multiple zeros. If there are at least two zeros, every product except self must contain at least one zero, so the entire result becomes all zeros. The algorithm handles this automatically because both prefix and suffix accumulators become zero during traversal.

Negative numbers are also important because sign changes can easily expose logic bugs. For example:

[-1,-2,-3,-4]

produces:

[-24,-12,-8,-6]

The prefix and suffix method works correctly because multiplication order and sign handling remain mathematically consistent throughout both passes.

A final edge case is the minimum valid input size of 2. With only two elements, each answer is simply the other element. The algorithm still works correctly because the prefix and suffix passes naturally produce the required products without requiring any special handling.