LeetCode 238: Product of Array Except Self

Problem Restatement

We are given an integer array nums.

We need to return an array answer where:

answer[i] = product of all nums[j] where j != i

We must solve it:

• In O(n) time
• Without using division

LeetCode gives this example:

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

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

Input and Output

Function shape:

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        ...

Examples

Example 1:

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

For each index:

answer[0] = 2 * 3 * 4 = 24
answer[1] = 1 * 3 * 4 = 12
answer[2] = 1 * 2 * 4 = 8
answer[3] = 1 * 2 * 3 = 6

Example 2:

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

Only index 2 gets a non-zero result, because nums[2] is the zero. Every other index still includes that zero in its product.

First Thought: Brute Force

For each index i, we can multiply every element except nums[i].

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

        for i in range(n):
            product = 1

            for j in range(n):
                if i != j:
                    product *= nums[j]

            ans.append(product)

        return ans

This is correct, but it is too slow.

For each of n positions, we scan n values.

So the time complexity is:

O(n^2)

We need a linear solution.

Key Insight

For each index i, the product except self can be split into two parts:

product of everything left of i
*
product of everything right of i

For:

nums = [1, 2, 3, 4]

At index 2, the value is 3.

The product except self is:

left side:  1 * 2
right side: 4

answer[2] = (1 * 2) * 4 = 8

So we do not need division.

We only need prefix products and suffix products.

Prefix and Suffix Products

A prefix product before index i means:

nums[0] * nums[1] * ... * nums[i - 1]

A suffix product after index i means:

nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

Then:

answer[i] = prefix_before_i * suffix_after_i

For nums = [1,2,3,4]:

The empty product is 1.

That is why the left product of the first element is 1, and the right product of the last element is 1.

Algorithm

We can store left products directly in the output array.

First pass, left to right:

1. Start left = 1.
2. For each index i:
   • Set ans[i] = left.
   • Update left *= nums[i].

After this pass, ans[i] contains the product of all numbers to the left of i.

Second pass, right to left:

1. Start right = 1.
2. For each index i from right to left:
   • Multiply ans[i] *= right.
   • Update right *= nums[i].

After this pass, each ans[i] has:

left product * right product

which is exactly the product of all values except nums[i].

Walkthrough

Use:

nums = [1, 2, 3, 4]

Start:

ans = [1, 1, 1, 1]
left = 1

First pass:

Now:

ans = [1, 1, 2, 6]

Second pass:

right = 1

Final result:

[24, 12, 8, 6]

Correctness

For each index i, after the first pass, ans[i] equals the product of all elements before i.

This is true because left starts at 1, and before processing index i, it contains exactly:

nums[0] * nums[1] * ... * nums[i - 1]

Then the second pass scans from right to left.

Before processing index i, right contains exactly:

nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

The algorithm multiplies:

ans[i] *= right

So ans[i] becomes:

product of all elements before i
*
product of all elements after i

This is exactly the product of all elements except nums[i].

Since this happens for every index, the algorithm returns the correct array.

Complexity

The output array is required by the problem, so it is usually not counted as extra space.

Implementation

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [1] * n

        left = 1
        for i in range(n):
            ans[i] = left
            left *= nums[i]

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

        return ans

Code Explanation

Create the output array:

ans = [1] * n

Then compute products to the left:

left = 1
for i in range(n):
    ans[i] = left
    left *= nums[i]

At index i, left does not include nums[i] yet. That is why it correctly represents the product of elements before i.

Then compute products to the right:

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

At index i, right does not include nums[i] yet. That is why it correctly represents the product of elements after i.

Finally:

return ans

Testing

def run_tests():
    s = Solution()

    assert s.productExceptSelf([1, 2, 3, 4]) == [24, 12, 8, 6]
    assert s.productExceptSelf([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
    assert s.productExceptSelf([2, 3]) == [3, 2]
    assert s.productExceptSelf([0, 0]) == [0, 0]
    assert s.productExceptSelf([5, 0, 2]) == [0, 10, 0]
    assert s.productExceptSelf([-1, -2, -3, -4]) == [-24, -12, -8, -6]

    print("all tests passed")

run_tests()