Arrays

Episode 7 Product of Array Except Self

6 min · LeetCode 238 · Java

Title card of Episode 7: Product of Array Except Self

▶ This video is coming to YouTube soon.

LeetCode 238, Product of Array Except Self, solved on screen. We start with three examples, including arrays with one zero and with two. Then we watch the brute force multiply all the other numbers for every index, read its code line by line, and see why it's O(n²). Finally, two passes do it in O(n) with no division: a running prefix product writes everything to the left of each slot, and a running suffix product multiplies in everything to the right.

What you'll learn

  • What the problem asks, through three worked examples (zeros included)
  • The brute force: a fresh product for every index, O(n²) time
  • The key idea: answer[i] = left product × right product
  • The two-pass prefix and suffix solution: O(n) time, O(1) extra space
  • Why the answer array doesn't count as extra space

Chapters

  1. 0:00The problem
  2. 0:13Examples
  3. 0:55Brute force, visualized
  4. 1:48Brute force: the code
  5. 2:02Brute force, line by line
  6. 2:47Prefix × suffix: the idea
  7. 3:04Prefix × suffix, visualized
  8. 4:06Prefix × suffix: the code
  9. 4:20Prefix × suffix, line by line
  10. 5:13Comparing the approaches