Skip to content

Volume ITechnology

4.4.7 — Product of Array Except Self ​

LeetCode 238 · Medium · ★ Blind 75

The problem ​

You are given a list of numbers called nums. Build a new list called answer. At each position i, answer[i] must be the product of every number in nums except nums[i]. A product is what you get when you multiply numbers together.

nums   = [1, 2, 3, 4]
answer = [24, 12, 8, 6]

nums   = [-1, 1, 0, -3, 3]
answer = [ 0, 0, 9,  0, 0]

Look at the first example. answer[0] skips the 1 and multiplies the rest: 2 \times 3 \times 4 = 24. answer[1] skips the 2: 1 \times 3 \times 4 = 12. And so on.

The list can have up to 100,000 numbers. There are two hard rules. You may not use division, and the solution must run in O(n) time. A follow-up asks you to use only O(1) extra memory, not counting the answer list itself.

What the problem is really asking ​

Pick any position, say position 2 in [1, 2, 3, 4]. The numbers that are not at position 2 fall into two groups.

  • The numbers to its left: 1 and 2.
  • The numbers to its right: 4.

So the answer at position 2 is (product of everything on the left) times (product of everything on the right) = (1 \times 2) \times 4 = 8.

That is true at every position. We can write it as one formula:

\text{answer}[i] = \Big(\prod_{j < i} \text{nums}[j]\Big) \times \Big(\prod_{j > i} \text{nums}[j]\Big)

Read it aloud like this. The big \prod sign, the Greek capital letter "pi", means "multiply together". So the first bracket says "multiply together nums[j] for every position j that is less than i", which is everything to the left. The second bracket does the same for every j greater than i, which is everything to the right.

So the problem is really: for every position, find the product of its left side and the product of its right side.

Why division is banned ​

Without the rule, there is a two-line answer. Multiply everything together once, then divide by each number in turn. For [1, 2, 3, 4] the total is 24, and 24 \div 2 = 12, which is correct.

But one zero breaks it. Dividing by zero is not allowed. To handle zeros properly you need three separate cases: no zeros, exactly one zero, or two or more zeros. Each case needs its own code.

The solution on this page has no special cases at all. Zeros and negative numbers go through the same lines as everything else. So the rule is not just a puzzle. It is pushing you toward a cleaner design.

The brute force, and where it wastes work ​

For each position, multiply all the other numbers.

python
def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        p = 1
        for j in range(n):
            if j != i:          # skip the number at position i
                p *= nums[j]
        answer.append(p)
    return answer

This does n multiplications for each of n positions, so about n^2 steps. For 100,000 numbers that is ten billion steps. Too slow.

The waste in one sentence: the product of everything left of position 5 is just the product of everything left of position 4, times one more number, but the brute force multiplies it all again from scratch.

The idea ​

Think of a train picking up passengers. To know how many people are on the train when it leaves station 5, you do not go back and count everyone who boarded at stations 1, 2, 3 and 4. You take the number who were on board leaving station 4, and add the people who got on at station 5.

We do the same with multiplication. Walk left to right, carrying a running product called prefix. At each position, prefix already holds the product of everything to the left. Write it down, then multiply in the current number so it is ready for the next position.

Then do the same thing from right to left with a running product called suffix, for everything to the right.

The figure shows both sweeps on [1, 2, 3, 4].

nums1234① left to right1126product of everything LEFT of i② right to left241241product of everything RIGHT of i ③ multiply241286left × right
Rows ① and ③ are the same array. The second sweep multiplies into what the first wrote.

Here is how to read it.

  1. The top row is nums.
  2. Row ① is the left-to-right sweep. Each blue box holds the product of everything to the left of that position. The first box is 1, because nothing is to the left of position 0.
  3. Row ② is the right-to-left sweep. Each amber box holds the product of everything to the right. The last box is 1, because nothing is to the right of the last position.
  4. Row ③ multiplies ① and ② position by position: 1 \times 24 = 24, 1 \times 12 = 12, 2 \times 4 = 8, 6 \times 1 = 6. That is the answer.

Why does the first left product start at 1 and not at nums[0]? Because there is nothing to the left of position 0. The product of no numbers at all is 1, in the same way that the sum of no numbers is 0. Multiplying by 1 changes nothing. Starting at 1 means position 0 needs no special if.

The solution ​

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

        prefix = 1                          # (2)
        for i in range(n):                  # (3)
            answer[i] = prefix              # (4)
            prefix *= nums[i]               # (5)

        suffix = 1                          # (6)
        for i in range(n - 1, -1, -1):      # (7)
            answer[i] *= suffix             # (8)
            suffix *= nums[i]               # (9)

        return answer
ts
function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array(n).fill(1);    // (1)

  let prefix = 1;                         // (2)
  for (let i = 0; i < n; i++) {           // (3)
    answer[i] = prefix;                   // (4)
    prefix *= nums[i];                    // (5)
  }

  let suffix = 1;                         // (6)
  for (let i = n - 1; i >= 0; i--) {      // (7)
    answer[i] *= suffix;                  // (8)
    suffix *= nums[i];                    // (9)
  }

  return answer;
}

Line by line ​

(1) answer = [1] * n. The output list, filled with 1s. The first sweep will overwrite every slot, so the starting value does not really matter here. Using 1 is a safe habit, because we will later multiply into these slots.

(2) prefix = 1. The running product of everything to the left of the current position. Before position 0, nothing is to the left, so it starts at 1.

(3) Sweep left to right, over positions 0, 1, 2, and so on.

(4) answer[i] = prefix. At this moment, prefix holds the product of every number before position i. It does not yet include nums[i]. So we write it into the answer slot.

(5) prefix *= nums[i]. Now fold the current number in. prefix becomes the product of everything up to and including position i, which is exactly "everything to the left" for the next position.

The order of lines (4) and (5) is the whole trick. If you swap them, prefix already includes nums[i] when you write it down. Every slot would then include its own number, which is the one thing the problem says to leave out.

(6) suffix = 1. The running product of everything to the right. Nothing is to the right of the last position, so it starts at 1.

(7) Sweep right to left. range(n - 1, -1, -1) counts down from the last position, n - 1, to 0. The middle number, -1, is where to stop, and Python stops before it, so 0 is the last position visited. The third number, -1, means "step backwards by one".

(8) answer[i] *= suffix. The slot already holds the left product from the first sweep. We multiply in the right product. Now the slot holds left times right, which is the final answer for this position.

(9) suffix *= nums[i]. Fold the current number in, ready for the position to its left. Same discipline as lines (4) and (5): use it, then update it.

A helpful way to remember both loops is to say this sentence before writing them: "prefix is the product of everything strictly before i, and suffix is the product of everything strictly after i." Then each loop is simply "use the value, then update it".

Trace ​

Take nums = [1, 2, 3, 4].

First sweep, left to right.

iprefix beforeanswer[i] set toprefix after
0111 × 1 = 1
1111 × 2 = 2
2222 × 3 = 6
3666 × 4 = 24

Now answer is [1, 1, 2, 6].

Second sweep, right to left.

isuffix beforeanswer[i] becomessuffix after
316 × 1 = 61 × 4 = 4
242 × 4 = 84 × 3 = 12
1121 × 12 = 1212 × 2 = 24
0241 × 24 = 2424 × 1 = 24

The final answer is [24, 12, 8, 6].

Why zeros need no special case ​

Take nums = [1, 0, 3].

  • The first sweep gives [1, 1, 0]. The 0 only enters prefix after position 1 has been written.
  • The second sweep multiplies in the right-hand products [0, 3, 1].
  • The result is [1 × 0, 1 × 3, 0 × 1] = [0, 3, 0].

Check it by hand. Skipping position 0 gives 0 \times 3 = 0. Skipping position 1 gives 1 \times 3 = 3. Skipping position 2 gives 1 \times 0 = 0. All correct.

The zero lands in exactly the slots that should see it, and never in its own slot. That is because no sweep ever multiplies nums[i] into answer[i]. Lines (4) and (8) always write before lines (5) and (9) update. Two zeros give all zeros for the same reason. Negative numbers just multiply like any other number.

Complexity, derived ​

Time. The first loop runs n times, and each turn does one assignment and one multiplication. The second loop also runs n times with one multiplication and one update. So the total is about 2n small steps. We drop the constant 2, because only the growth matters, and get O(n).

Space. The answer list has n slots, but the problem says the output does not count as extra memory. Apart from it, we only use two numbers, prefix and suffix. So the extra memory is O(1).

A gentler first version builds two separate lists, left[] and right[], and then multiplies them. That is easier to read but uses O(n) extra memory. It is a perfectly good first answer in an interview. Then show how to fold left[] into answer and replace right[] with one variable. Showing the improvement step by step is better than jumping to the tight version.

Edge cases ​

  • Two numbers, the smallest input allowed. [a, b] gives [b, a].
  • One zero. Every slot except the zero's own slot becomes 0.
  • Two or more zeros. Every slot becomes 0.
  • Overflow. The problem promises that every left product and right product fits in a 32-bit whole number. That promise is about the running products, not only the final answers, because those are what could grow too large. Python and JavaScript numbers do not overflow at this size. In Java or C++ they could.

Variations you will meet ​

  • Prefix sums. The same two-sweep idea with addition instead of multiplication. See 4.2.
  • Trapping Rain Water. The water above each bar is limited by the tallest bar on its left and the tallest bar on its right. That is this exact structure with max instead of ×. See 4.5.5.
  • Candy. Children in a row must get more sweets than a neighbour with a higher rating. One sweep handles the left neighbour rule, one sweep handles the right neighbour rule, and each child gets the larger of the two.

The general lesson: when the answer at each position depends on everything before it and everything after it, do one sweep in each direction and choose the operation that fits the question.

What the interviewer will push on ​

"Why forbid division?" They want to see that you understand zeros. Division needs three separate cases for zeros. This solution needs none.

"Can you do it in O(1) extra memory?" Use the output list to hold the left products, and keep the right product in one variable.

"What if the numbers were decimals?" Even without zeros, division stops being safe. Decimal multiplication and division on a computer are not exact opposites, so small rounding errors creep in. This solution never divides.

"What if the list keeps changing, and you must answer many queries?" Every change would spoil the two sweeps. The right tool becomes a segment tree, which can update one number and answer a product query in O(\log n) time. See 4.13.4.

One thing to volunteer: say the rule about prefix and suffix out loud before writing the loops. That is how you know the code is correct, rather than hoping the examples pass.

Next: 4.4.8 Valid Sudoku. Back to sets, where the interesting part is how to name a region of a grid with one number.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet