DSA sheet · Arrays · Prefix sum pattern

Product of Array Except Self

This is the third problem of the prefix sum pattern. It is not a classic "add things up" prefix sum. Here we build running products: one coming from the left, one coming from the right. The teacher first writes the slow, obvious solution (for every index, multiply everything else), shows why it is too slow for n = 10⁵, goes through the four array patterns to pick the right one, and then reuses already-computed products so the whole job takes just two simple loops. She also says this question is asked in interviews again and again, so it is worth learning well.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: multiply everything except me
• Part B · Optimal: left products, then right products
• Part C · Revision page

Part 0 · Before starting

What is a prefix sum?

A prefix of an array is a piece that starts at index 0 and stops somewhere: nums[0..i]. The prefix sum at index i is the total of that piece: prefix[i] = nums[0] + nums[1] + … + nums[i].

We never add the whole piece again from scratch. Each cell is built from the cell just before it: prefix[i] = prefix[i-1] + nums[i]. "Everything up to i−1" is already saved, so we only add one new number.

Why sum(l..r) = prefix[r] − prefix[l−1]

prefix[r] is the total of indexes 0…r. prefix[l−1] is the total of 0…l−1. Subtract, and the shared part 0…l−1 cancels. What is left is exactly l…r. Example: sum(1..3) = 3 + 4 + 5 = 12 = prefix[3] − prefix[0] = 14 − 2 ✓.

The "−1" trick: when l = 0 there is no prefix[-1]. We treat the empty prefix (nothing taken yet) as 0, because adding nothing gives 0. Many solutions store this as an extra cell at the start, or as {0: -1} in a hashmap.

The same idea with products: prefix product and suffix product

Replace "+" with "×" and you get a prefix product: the product of everything up to some index. A suffix is a piece that ends at the last index (nums[i..n−1]), so a suffix product is the product of everything from some index to the end.

For "empty" we now use 1, not 0, because multiplying by 1 changes nothing (just as adding 0 changes nothing). If nothing is on the left of index 0, its left product is 1.

The four array patterns (the teacher's checklist for optimising)

Part A · Brute force: multiply everything except me

LeetCode 238

1The question in simple words

You get an integer array nums. Build a new array answer of the same length where answer[i] = the product of all the other numbers, i.e. everything except nums[i] itself.

For index 0 we skip the 1 and multiply 2 × 3 × 4 = 24. For index 1 we skip the 2 and multiply the left side (1) with the right side (3 × 4): 12.

The catch: you are not allowed to use division.

2What the constraints tell us

• 2 <= nums.length <= 10⁵ → at least 2 numbers, so every index has at least one "other" number. And n is big: an O(n²) solution means 10¹⁰ steps. About 10⁸ steps is the safe limit, so n² will get TLE. We'll need something better.
• -30 <= nums[i] <= 30 → numbers can be negative and can be 0. Our method must not depend on signs, and zeros must work.
• LeetCode also promises every prefix and suffix product fits in a 32-bit integer, so in Java/C++ int is enough. Python ints never overflow anyway.

3Intuition: how would you do it by hand?

Point at one index; call that finger left. Now run a second finger, right, across the whole array from start to end, multiplying every number it touches, but skip the moment right lands on the same index as left. When right reaches the end, the product is the answer for that index. Then move left forward by one and repeat.

Worked example: nums = [2, 3, 4, 5], answer for index 0

Left is on index 0 (the 2). Right starts at 0: same as left → skip. Right at 1: product = 3. Right at 2: 3 × 4 = 12. Right at 3: 12 × 5 = 60. Store 60 in answer[0].

4Building the logic from examples

Where should the right finger start?

How do we "skip" ourselves?

Inside the inner loop: if right == left, do nothing for this step (continue). Otherwise multiply product *= nums[right].

What should product start at, and what should answer start at?

• product starts at 1: multiplying by 1 changes nothing. (Starting at 0 would make every answer 0.)
• The result array can start filled with 0s.

5Approach steps

1. Make res of size n.
2. For each left from 0 to n − 1: set product = 1.
3. For each right from 0 to n − 1: if right == left, skip; else product *= nums[right].
4. After the inner loop, res[left] = product.
5. Return res.

6Code (Python)

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        res = [0] * n                      # will be overwritten
        for left in range(n):              # the index we answer for
            product = 1
            for right in range(n):         # walk the WHOLE array
                if right == left:          # skip myself
                    continue
                product *= nums[right]
            res[left] = product
        return res

7Code line by line

8Dry run (hand table)

nums = [2, 3, 4, 5]. Each row is one value of left; "skip" marks where right == left.

Answer [60, 40, 30, 24] ✓. Notice how often we redo the same work: "2 × 3" is computed again in rows 2 and 3. Part B removes exactly this waste.

9Complexity & remember

• Time O(n²): for each of the n left positions, right walks all n positions. For n = 10⁵ that is 10¹⁰ steps, far above ~10⁸ → TLE.
• Space O(1) extra (plus the output array).

Part B · Optimal: left products, then right products

1The question

Same question, same "no division" rule. We want O(n).

2Constraints → which pattern?

n up to 10⁵ means we need about O(n). The teacher goes through the four patterns one by one:

• Two pointers ✗: that pattern only looks at the two numbers under the pointers. Here, for one index we need everything else.
• Sliding window ✗: a window is one continuous block. Our "everything except i" has a hole in the middle (left part + right part), so it isn't one window.
• Kadane's ✗: it is for the maximum sum with negatives. We want products for every index, not a max.
• Prefix sum ✓: compute running results once and reuse them. It's not a sum here, but the idea of "save what you computed, reuse it for the next index" fits exactly.

3Intuition

Split the answer in two: answer[i] = (product of everything left of i) × (product of everything right of i).

nums:        2     3    [4]    5
             \_____/          \_/
           left part = 6   right part = 5      answer[2] = 6 × 5 = 30

Both parts are running products. Walk left → right once to get every left part. Walk right → left once to get every right part. Multiply them together. Two separate loops, no loop inside a loop.

4Building the logic from examples

Pass 1: left products, stored straight into res

Use nums = [2, 3, 4, 5].

• Index 0 (the 2): nothing is on its left. The left product is the empty product = 1. This is true whatever the value at index 0 is. So res[0] = 1.
• Index 1 (the 3): its left side is just [2]. Look at what we already have: res[0] holds "everything left of index 0" (= 1), and nums[0] is 2. Multiply: 1 × 2 = 2. That is "everything left of index 1".
• Index 2 (the 4): res[1] × nums[1] = 2 × 3 = 6.
• Index 3 (the 5): res[2] × nums[2] = 6 × 4 = 24. We did not multiply 2 × 3 × 4 again; we reused the 6.

Pass 2: right products, from the back

Now walk from the last index to the first, keeping a running right_prod = "product of everything to the right of where I stand".

• Index 3 (the 5): nothing on its right → right_prod = 1. res[3] = 24 × 1 = 24. Then, before moving left, put this 5 into the running product: right_prod = 1 × 5 = 5.
• Index 2 (the 4): left part is res[2] = 6 (same index this time, not i−1), right part is right_prod = 5. res[2] = 6 × 5 = 30 ✓ (2 × 3 × 5). Update: right_prod = 5 × 4 = 20.
• Index 1 (the 3): res[1] = 2 × 20 = 40 ✓. Update: right_prod = 20 × 3 = 60.
• Index 0 (the 2): res[0] = 1 × 60 = 60 ✓. Update: right_prod = 120 (not used any more).

5Approach steps

1. res = [1] * n (so res[0] = 1, the empty left product).
2. For i from 1 to n − 1: res[i] = res[i-1] * nums[i-1].
3. right_prod = 1.
4. For i from n − 1 down to 0: res[i] *= right_prod, then right_prod *= nums[i].
5. Return res.

6Code (Python)

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        res = [1] * n
        res[0] = 1                          # nothing on the left of index 0

        # pass 1: res[i] = product of everything LEFT of i
        for i in range(1, n):
            res[i] = res[i - 1] * nums[i - 1]

        # pass 2: multiply in the product of everything RIGHT of i
        right_prod = 1                      # nothing on the right of the last index
        for i in range(n - 1, -1, -1):
            res[i] = res[i] * right_prod
            right_prod *= nums[i]           # include nums[i] for the next index (i-1)

        return res

7Code line by line

8Dry run (hand table)

nums = [2, 3, 4, 5].

Pass 1 (left → right)

Pass 2 (right → left)

Matches the brute force ✓.

What happens with zeros?

No special code is needed. nums = [1, 2, 0, 4]: left products [1, 1, 2, 0], right products [0, 0, 4, 1] → answer [0, 0, 8, 0]. Only the zero's own index gets a non-zero answer (1 × 2 × 4). With two zeros, e.g. [0, 2, 0], every index still has some zero among the others → [0, 0, 0]. The division trick would crash here; this method doesn't care.

9Complexity & remember

• Time O(n): one loop forward, one loop backward, one after the other (not nested). That is n + n = 2n steps, which is O(n).
• Space O(n) for the answer array we must return. Apart from that we use only one variable (right_prod), so the extra space is O(1). (LeetCode's follow-up asks for exactly this: O(1) extra space, not counting the output.)

Part C · Revision page

s = Solution()
print(s.productExceptSelf([1, 2, 3, 4]))       # [24, 12, 8, 6]
print(s.productExceptSelf([2, 3, 4, 5]))       # [60, 40, 30, 24]
print(s.productExceptSelf([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]
print(s.productExceptSelf([0, 2, 0]))          # [0, 0, 0]
print(s.productExceptSelf([3, 4]))             # [4, 3]

Based on this video: Product of Array Except Self | Prefix Sum pattern