~20 minutes · Day 3 · prefix × suffix · Python
Tonight's problem is Product of Array Except Self. It is an interview favorite because the tempting shortcut, division, is blocked. The useful skill is learning how to answer “everything except this spot” by carrying what is on the left and what is on the right.
answer[i] = product of everything to the left times product of everything to the right; two sweeps, no division.
That's the whole pattern. For each index, the current number is not allowed to help its own answer. So the answer must be built from two outside pieces: everything before it, and everything after it.
The middle value is excluded; only the product before it and the product after it are allowed into its answer.
The LeetCode statement asks for an output array where each position holds the product of every other number. The obvious brute force is O(n^2): for each index, scan the whole list and multiply every value except that index.
def product_except_self(nums):
ans = []
for i in range(len(nums)):
prod = 1
for j, x in enumerate(nums):
if i != j: # skip only the current index
prod *= x
ans.append(prod)
return ans
This works, but it repeats almost all the same multiplication again for the next index. Division would seem tempting, but zero values break simple division, and the problem asks for a no-division solution. The prefix/suffix method works because it never divides.
First sweep left to right: store the product of everything before i. Second sweep right to left: carry the product of everything after i and multiply it into the answer. Python's range can count backward with a negative step.
def product_except_self(nums):
ans = [1] * len(nums) # answer starts neutral
left = 1
for i, x in enumerate(nums):
ans[i] = left # product before i
left *= x # include x for the next index
right = 1
for i in range(len(nums) - 1, -1, -1):
ans[i] *= right # product before i times after i
right *= nums[i] # include nums[i] for the next index left
return ans
The answer array does double duty: after the first sweep, it holds left products. After the second sweep, each cell has left product times right product.
The first pass writes products from the left; the second pass walks backward and turns those saved values into final answers.
A shop records shelf multipliers: [2, 3, 4, 5]. For each shelf, return the product of all other shelves. Before opening the answer: after the first sweep, what should each cell hold? What should the right sweep multiply in?
multipliers = [2, 3, 4, 5]
left_after_first_sweep = [1, 2, 6, 24]
right_product_each_index = [60, 20, 5, 1]
answer = [60, 40, 30, 24]At index 2, the left product is 2 * 3 and the right product is 5, so the answer is 30. Same invariant: left product times right product.
| Approach | Time | Space |
|---|---|---|
| Brute force (multiply every other value) | O(n^2) | O(1) extra |
| Prefix × suffix (two sweeps) | O(n) | O(1) extra |
The win is not a clever formula. It is separating “everything except me” into the left side and the right side.
1. What does answer[i] mean in this pattern?
2. Why is simple division the wrong habit here?
3. Spot the bug in this second sweep:
right = 1
for i in range(len(nums)):
ans[i] *= right
right *= nums[i]4. Which problem has this prefix/suffix shape?
Solve Product of Array Except Self in your Notion tracker with the cycle — predict → attempt → compare → encode:
Watch NeetCode — Product of Array Except Self at the compare step. Listen for how he separates the left product from the right product.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.