LeetCode 238 - Product of Array Except Self

This is a Medium array problem where each position needs the product of every element except itself. The constraint that makes the problem interesting is that division cannot be used, so the solution has to build the result from left products and right products.

---

Problem link and explanation

• Problem link: 238. Product of Array Except Self
• Summary: Given an integer array nums, return an array where each index contains the product of all elements except the one at that index.

For example:

nums = [1, 2, 3, 4]

Each result value is the product of everything except the current element.

index 0: 2 * 3 * 4 = 24
index 1: 1 * 3 * 4 = 12
index 2: 1 * 2 * 4 = 8
index 3: 1 * 2 * 3 = 6

So the result is:

[24, 12, 8, 6]

At first, computing the total product and dividing by the current element may seem enough. But division is not allowed, and zeros would require additional handling anyway. Instead, each index can be split into the product of everything on the left and the product of everything on the right.

---

Approach

1. Store left accumulated products

The product except self can be divided into two parts: the product of values to the left of the current index and the product of values to the right.

For nums = [1, 2, 3, 4], the value at index 2 is 3. The product except itself is the left product 1 * 2 multiplied by the right product 4.

I first initialize the answer array with 1s, then scan from left to right and store the accumulated product of the values on the left.

n = len(nums)
answer = [1] * n
acc = 1

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

After this loop, answer contains the left product for each index.

nums   = [1, 2, 3, 4]
answer = [1, 1, 2, 6]

Index 0 has no values on its left, so it stays 1. Since 1 is the identity value for multiplication, this handles the empty side naturally.

2. Multiply right accumulated products

Next, I scan from right to left and keep the accumulated product of the values on the right. Instead of storing a separate right-product array, I multiply that value directly into answer.

acc = 1

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

The first pass already stored the left product in answer, so the second pass only needs to multiply in the right product.

left product  = [1, 1, 2, 6]
right product = [24, 12, 4, 1]
result        = [24, 12, 8, 6]

This also works when the input contains zero because the result is built through actual left and right products, not by dividing a total product.

---

Complexity analysis

• Time complexity: O(n)

  • The array is scanned once from the left and once from the right. The total work is 2n, which is O(n).

• Space complexity: O(n)

  • The answer array stores the result. Under the LeetCode convention where the output array is not counted as extra space, the extra space is O(1) because only the accumulator and index variables are used.

---

Implementation code

The final implementation stores left accumulated products in answer first, then multiplies right accumulated products during the second pass.

from typing import List

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

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

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

        return answer

---

Summary and reflection

Because division is not allowed, the total product approach does not fit the constraint. Splitting each index into a left accumulated product and a right accumulated product gives the needed value without division.

In this solution, answer first stores the left products, and a single accumulator is used to multiply in the right products during the second pass.