LeetCode 238 · Arrays & Hashing

Product of Array Except Self, explained with a picture

Two runners multiplying from each end.

MediumArrays & Hashing
▶ Watch it step by step

The problem

Given a list of numbers, build a new list where each position holds the product of all the other numbers (everything except itself). Division is not allowed.

Input:  [1, 2, 3, 4]
Output: [24, 12, 8, 6]   (e.g. 24 = 2·3·4)

Picture it

Picture people standing in a row, each holding a number. A runner walks left to right carrying the product of everyone they have passed, and writes that onto each person’s card before multiplying in that person’s number. A second runner walks back from the right doing the same. Each card ends up holding (everything to my left) × (everything to my right), which is everyone except me.

How to recognise it

  • Each position needs a summary of everything except itself (a product, sum, maximum).
  • "Everything except i" splits into two parts: everything to the left and everything to the right.
  • The easy shortcut (total ÷ nums[i]) is forbidden, and it would break on zeros anyway.
  • n is up to 10^5, so recomputing the product for every position is too slow.

Start with brute force

For every position, multiply all the other numbers together.

def product_except_self_brute(nums):
    n = len(nums)
    out = []
    for i in range(n):
        p = 1
        for j in range(n):
            if j != i:
                p *= nums[j]
        out.append(p)
    return out

That is n − 1 multiplications for each of n positions: O(n²) time and O(1) extra space besides the output. With n = 10^5 it is about 10^10 multiplications, far too slow.

From brute force to the idea

  1. Find the waste. Position 5 and position 6 share almost all their work: both multiply nums[0] to nums[4] on the left, and both multiply the numbers after 6 on the right.
  2. Split the product. The answer at i is (product of everything left of i) × (product of everything right of i).
  3. Left products in one pass. Walk left to right with a running product left. Write it into out[i] before multiplying in nums[i], so position i only sees what is strictly to its left.
  4. Right products in a second pass. Walk right to left with a running product right, multiplying it into out[i] before multiplying in nums[i].
  5. No extra arrays. The output list holds the left products, and right is a single number. LeetCode does not count the output as extra space, so this meets the follow-up of O(1) extra space.

This is the key idea: answer = prefix product × suffix product, built with two running products.

The key idea

Answer[i] = prefix product before i × suffix product after i. Two passes, no division, O(n) time.

Python solution

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left              # product of everything on the left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right            # times everything on the right
        right *= nums[i]
    return out

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): each position multiplies n − 1 numbersO(1) extra besides the output
Two running products (shown code)O(n): two passes, one multiplication each per positionO(1) extra besides the output: left and right

Edge cases

  • One zero ([-1, 1, 0, -3, 3]): returns [0, 0, 9, 0, 0]. Only the zero's own position escapes the zero.
  • Two or more zeros ([0, 0, 2]): every position includes at least one zero, so the result is all zeros.
  • Negative numbers: handled by ordinary multiplication; no special case.
  • Two numbers ([2, 3]): returns [3, 2], the minimum LeetCode allows.
  • One number or empty list: returns [1] and []. These are outside LeetCode's limits (n ≥ 2); [1] is the empty product.
  • Overflow: LeetCode promises every prefix and suffix product fits in 32 bits. Python integers never overflow anyway.

Common mistakes

  • Multiplying left *= nums[i] before writing out[i] = left, so each position includes itself. For [1, 2, 3, 4] that returns [24, 24, 24, 24].
  • Using division and then special-casing zeros, which the problem forbids.
  • Building separate prefix and suffix arrays. Correct and O(n), but it uses O(n) extra space that the follow-up asks you to avoid.
Your turn: division allowed, zeros included

Now suppose division is allowed. Solve the same problem with a total product and division, and make it correct when the list contains zeros. Describe your approach, then write it if you like.

Compare with our answer

Count the zeros and multiply all the non-zero numbers. Two or more zeros make every answer 0. Exactly one zero means only that position gets the product of the others; everything else is 0. With no zeros, divide the total by each number.

def product_with_division(nums):
    zeros = nums.count(0)
    total = 1
    for x in nums:
        if x != 0:
            total *= x
    if zeros > 1:
        return [0] * len(nums)
    if zeros == 1:
        return [total if x == 0 else 0 for x in nums]
    return [total // x for x in nums]

total // x is exact here because x divides the total. Time O(n), extra space O(1).

A strong answer mentions: the three zero cases, multiplying only the non-zero numbers, and that integer division is exact because each x is a factor of the total.

Check what stuck

1. For each day you must report the highest temperature on any other day. Which approach fits best?

2. Why does the shown code use O(1) extra space even though it returns a list of n numbers?

3. A learner swaps the two lines of the first loop, so left *= nums[i] runs before out[i] = left. What does the function return for [1, 2, 3, 4]?

Score 60% or more and the lesson is marked complete.