{ "cells": [ { "cell_type": "markdown", "id": "df550714c524", "metadata": {}, "source": [ "# Product of Array Except Self\n", "\n", "| Field | Value |\n", "|------------|-----------------------------------------|\n", "| Source | [link](https://leetcode.com/problems/product-of-array-except-self/) |\n", "| Difficulty | Medium |\n", "| Topics | `array`, `prefix sum`, `prefix product` |\n", "| Date | 2026-10-09 |\n", "| Status | Solved |" ] }, { "cell_type": "markdown", "id": "ffc3f32d0d9a", "metadata": {}, "source": [ "## 1. Problem\n", "\n", "> Given an integer array `nums`, return an array `output` where `output[i]` is the product of all\n", "> the elements of `nums` except `nums[i]`. Each product is guaranteed to fit in a 32-bit integer.\n", ">\n", "> **Follow-up:** Could you solve it in $O(n)$ time **without using the division operation**?\n", "\n", "**Example 1**\n", "```\n", "Input: nums = [1, 2, 4, 6]\n", "Output: [48, 24, 12, 8]\n", "```\n", "\n", "**Example 2**\n", "```\n", "Input: nums = [-1, 0, 1, 2, 3]\n", "Output: [0, -6, 0, 0, 0]\n", "```\n", "\n", "**Constraints**\n", "- `2 <= len(nums) <= 10^5`\n", "- `-30 <= nums[i] <= 30`\n", "- The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit integer." ] }, { "cell_type": "markdown", "id": "fa6eb4e251fe", "metadata": {}, "source": [ "## 2. Thinking\n", "\n", "- **Brute force idea:** for each `i`, multiply every other element: $O(n^2)$. Too slow at $n = 10^5$.\n", "- **Division idea:** total product $P$, then `output[i] = P / nums[i]`: $O(n)$. But it breaks on\n", " zeros (need special cases for 0, 1, or 2+ zeros), and the follow-up forbids division.\n", "- **Key insight:** \"everything except `i`\" = **everything to the left of `i`** × **everything to\n", " the right of `i`**:\n", " $$\\text{output}[i] = \\underbrace{\\textstyle\\prod_{ji} \\text{nums}[j]}_{\\text{suffix}}$$\n", " Both are running products, so one left-to-right pass and one right-to-left pass give every\n", " answer in $O(n)$ with no division. Zeros need no special handling.\n", "- **Space trick:** store the prefix products directly in `output`, then sweep right-to-left\n", " multiplying in a single running `suffix` variable → $O(1)$ extra space (the output array\n", " doesn't count).\n", "- **Edge cases to remember:** one zero (only its own position is non-zero), two or more zeros\n", " (everything is 0), negative numbers, length 2 (`[a, b]` → `[b, a]`)." ] }, { "cell_type": "markdown", "id": "c0b8c5462569", "metadata": {}, "source": [ "### Walkthrough of the best solution (Approach C)\n", "\n", "**The idea:** for position `i`, \"everything except `nums[i]`\" splits into two parts:\n", "\n", "```\n", "nums = [ a, b, c, d, e ]\n", " ↑ i = 2\n", "everything except c = (a × b) × (d × e)\n", " left part right part\n", " = prefix = suffix\n", "```\n", "\n", "**By hand**, for `nums = [1, 2, 4, 6]` (\"nothing\" counts as **1**, which is why `prefix` and\n", "`suffix` both start at 1):\n", "\n", "| i | nums[i] | left of i | prefix | right of i | suffix | prefix × suffix |\n", "|---|---|---|---|---|---|---|\n", "| 0 | 1 | (nothing) | **1** | 2·4·6 | **48** | 48 |\n", "| 1 | 2 | 1 | **1** | 4·6 | **24** | 24 |\n", "| 2 | 4 | 1·2 | **2** | 6 | **6** | 12 |\n", "| 3 | 6 | 1·2·4 | **8** | (nothing) | **1** | 8 |\n", "\n", "**Pass 1, left to right:** store the prefix product in `result`.\n", "\n", "```python\n", "prefix = 1\n", "for i in range(n):\n", " result[i] = prefix # ① store \"product of everything LEFT of i\"\n", " prefix *= nums[i] # ② then include nums[i] for the next position\n", "```\n", "\n", "| i | ① result[i] = prefix | ② prefix *= nums[i] | result after |\n", "|---|---|---|---|\n", "| 0 | result[0] = 1 | prefix = 1·1 = 1 | [1, 1, 1, 1] |\n", "| 1 | result[1] = 1 | prefix = 1·2 = 2 | [1, 1, 1, 1] |\n", "| 2 | result[2] = 2 | prefix = 2·4 = 8 | [1, 1, 2, 1] |\n", "| 3 | result[3] = 8 | prefix = 8·6 = 48 | [1, 1, 2, 8] |\n", "\n", "**The order of ① and ② is the key detail:** store first, multiply after. When `result[i]` is\n", "written, `prefix` doesn't include `nums[i]` yet, so position `i` is left out. Swap the lines and\n", "every position includes itself.\n", "\n", "**Pass 2, right to left:** multiply in the suffix product, kept in one running variable.\n", "\n", "```python\n", "suffix = 1\n", "for i in range(n - 1, -1, -1):\n", " result[i] *= suffix # ① result[i] = prefix × \"product RIGHT of i\"\n", " suffix *= nums[i] # ② then include nums[i] for the next position (to the left)\n", "```\n", "\n", "| i | ① result[i] *= suffix | ② suffix *= nums[i] | result after |\n", "|---|---|---|---|\n", "| 3 | 8 × 1 = **8** | suffix = 1·6 = 6 | [1, 1, 2, 8] |\n", "| 2 | 2 × 6 = **12** | suffix = 6·4 = 24 | [1, 1, 12, 8] |\n", "| 1 | 1 × 24 = **24** | suffix = 24·2 = 48 | [1, 24, 12, 8] |\n", "| 0 | 1 × 48 = **48** | suffix = 48·1 = 48 | [48, 24, 12, 8] ✓ |\n", "\n", "**Why one variable instead of a suffix array?** Each suffix value is used once, exactly when the\n", "right-to-left pass reaches that position, so a running variable is enough. The only array is\n", "`result` (the output doesn't count), so extra space is $O(1)$.\n", "\n", "**Why zeros need no special case**, for `nums = [-1, 0, 1, 2, 3]`:\n", "- Pass 1 gives `result = [1, -1, 0, 0, 0]`. Once `prefix` passes the 0, it stays 0.\n", "- Pass 2, right to left:\n", " - i=4: 0 × 1 = 0, then suffix = 3\n", " - i=3: 0 × 3 = 0, then suffix = 6\n", " - i=2: 0 × 6 = 0, then suffix = 6\n", " - i=1: −1 × 6 = **−6**, then suffix = 0\n", " - i=0: 1 × 0 = 0\n", "- Result `[0, -6, 0, 0, 0]` ✓. The zero's own position skips the zero on both sides, so it\n", " gets the real product. Every other position picks up the zero from one side. Nothing is\n", " divided, so nothing special is needed.\n", "\n", "**Summary:** answer = left product × right product. In each pass, **use the running product,\n", "then multiply in `nums[i]`**. That order is what leaves `nums[i]` out." ] }, { "cell_type": "code", "id": "0e6158592d4d", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "# Setup: run this cell first. Lets you run pytest tests inside the notebook.\n", "try:\n", " import ipytest\n", "except ImportError: # Colab and other fresh kernels don't ship ipytest\n", " %pip install -q ipytest\n", " import ipytest\n", "import pytest\n", "\n", "ipytest.autoconfig()" ] }, { "cell_type": "markdown", "id": "a91d7523966d", "metadata": {}, "source": [ "## 3. Solution\n", "\n", "### Approach A — my version (total product + division, zero counting)\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(1)$ extra. It's correct and the Big-O is already optimal,\n", "but it doesn't answer the question being asked:\n", "1. **It uses division**, which the follow-up rules out. Division is also the fragile part: it\n", " needs the three zero cases (0, 1, 2+ zeros), and `//` only works because the division is\n", " always exact (`//` floors, so a non-exact case with negatives would be wrong). In C++/Java\n", " the full product can also overflow even when every answer fits.\n", "2. **Several passes:** `nums.count(0)`, `math.prod(nums)`, then the division pass; in the\n", " one-zero case it adds an `enumerate` pass plus a filtered copy of the list. They're mostly\n", " C-level loops, so it's still quick in Python.\n", "3. Small things: `result` is built before the early return even when unused; `prod != 0` is\n", " just `zero_count == 0` again; the comprehension reuses the name `num` from the outer loop.\n", "\n", "The code is unchanged except for the signature and comments." ] }, { "cell_type": "code", "id": "4fc1068f98ad", "metadata": {}, "source": [ "import math\n", "from itertools import accumulate\n", "from operator import mul\n", "\n", "def product_except_self_mine(nums: list[int]) -> list[int]:\n", " zero_count = nums.count(0) # pass 1\n", " result = [0 for _ in range(len(nums))]\n", " if zero_count > 1:\n", " return result\n", " prod = math.prod(nums) # pass 2\n", "\n", " if prod != 0: # same as zero_count == 0\n", " return [prod // num for num in nums] # DIVISION: what the follow-up forbids\n", " for index, num in enumerate(nums): # pass 3 (one-zero case only)\n", " if num == 0:\n", " new_prod = math.prod([num for num in nums if num != 0]) # copies the list\n", " result[index] = new_prod\n", " return result" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "f029dcd7f88c", "metadata": {}, "source": [ "### Approach B — prefix and suffix arrays\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(n)$ extra.\n", "`prefix[i]` = product of everything left of `i`, `suffix[i]` = product of everything right of `i`;\n", "the answer is `prefix[i] * suffix[i]`. The easiest version to derive on a whiteboard: write it\n", "first, then optimise the space away (Approach C)." ] }, { "cell_type": "code", "id": "69aed80a2ead", "metadata": {}, "source": [ "def product_except_self_arrays(nums: list[int]) -> list[int]:\n", " n = len(nums)\n", " prefix = [1] * n\n", " suffix = [1] * n\n", " for i in range(1, n):\n", " prefix[i] = prefix[i - 1] * nums[i - 1]\n", " for i in range(n - 2, -1, -1):\n", " suffix[i] = suffix[i + 1] * nums[i + 1]\n", " return [p * s for p, s in zip(prefix, suffix)]" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "a087774c086f", "metadata": {}, "source": [ "### Approach C — prefix in the output, running suffix ✅ best practice (interview answer)\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(1)$ extra (output not counted).\n", "Pass 1 writes the prefix products into `result`. Pass 2 walks right-to-left keeping the suffix\n", "product in one variable and multiplies it in. No division, no zero cases, two passes." ] }, { "cell_type": "code", "id": "5147992d6d5d", "metadata": {}, "source": [ "def product_except_self(nums: list[int]) -> list[int]:\n", " n = len(nums)\n", " result = [1] * n\n", " prefix = 1\n", " for i in range(n):\n", " result[i] = prefix # product of nums[:i]\n", " prefix *= nums[i]\n", " suffix = 1\n", " for i in range(n - 1, -1, -1):\n", " result[i] *= suffix # times product of nums[i+1:]\n", " suffix *= nums[i]\n", " return result" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "3aa7c63416aa", "metadata": {}, "source": [ "### Approach D — `itertools.accumulate` (Pythonic)\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(n)$ extra.\n", "Same prefix × suffix idea, but the running products are computed in C by `accumulate`.\n", "`initial=1` shifts them by one so `prefix[i]` excludes `nums[i]`. Short, but it uses $O(n)$\n", "extra space and wasn't faster than C in the timing below. Good to know `accumulate`; in an\n", "interview, write C." ] }, { "cell_type": "code", "id": "800c2fab036c", "metadata": {}, "source": [ "def product_except_self_accumulate(nums: list[int]) -> list[int]:\n", " prefix = list(accumulate(nums, mul, initial=1)) # prefix[i] = prod(nums[:i])\n", " suffix = list(accumulate(reversed(nums), mul, initial=1)) # suffix[j] = prod of last j\n", " # output[i] = prefix[i] * suffix[n-1-i]; map/zip stop at the shorter, all in C\n", " return list(map(mul, prefix, reversed(suffix[:-1])))" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "af1f22386d90", "metadata": {}, "source": [ "## 4. Tests\n", "\n", "Every approach runs against every case. None of them mutate `nums`." ] }, { "cell_type": "code", "id": "f0e9d0be54a6", "metadata": {}, "source": [ "%%ipytest -q\n", "\n", "APPROACHES = [\n", " product_except_self_mine,\n", " product_except_self_arrays,\n", " product_except_self,\n", " product_except_self_accumulate,\n", "]\n", "\n", "CASES = [\n", " ([1, 2, 4, 6], [48, 24, 12, 8]),\n", " ([-1, 0, 1, 2, 3], [0, -6, 0, 0, 0]),\n", " ([3, 5], [5, 3]), # minimum length: answers swap\n", " ([0, 4], [4, 0]), # one zero at the start\n", " ([4, 0], [0, 4]), # one zero at the end\n", " ([0, 0], [0, 0]), # only zeros\n", " ([1, 0, 2, 0], [0, 0, 0, 0]), # two zeros: everything is 0\n", " ([-2, -3, 4], [-12, -8, 6]), # negatives (exact // with negatives)\n", " ([-1, -1, -1, -1], [-1, -1, -1, -1]), # all negative\n", " ([1] * 100_000, [1] * 100_000), # max size\n", "]\n", "\n", "@pytest.mark.parametrize(\"fn\", APPROACHES)\n", "@pytest.mark.parametrize(\"nums, expected\", CASES)\n", "def test_product_except_self(fn, nums, expected):\n", " assert fn(nums) == expected" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "53f8e003a544", "metadata": {}, "source": [ "## 5. Scratch / Experiments\n", "\n", "Max size $n = 10^5$. Random values would make the product astronomically large (Python ints\n", "never overflow, so it would measure bigint arithmetic), so to respect the \"fits in 32 bits\"\n", "constraint the input is mostly $\\pm 1$ with a few $2$s. Two inputs: no zeros, and one zero\n", "(the extra-pass branch of Approach A).\n", "\n", "Typical results (ms, $n = 10^5$):\n", "\n", "| Approach | no zero | one zero |\n", "|---|---|---|\n", "| A mine (division) | ~6 | ~7.4 |\n", "| B prefix + suffix arrays | ~13–17 | ~13 |\n", "| C prefix in output ✅ | ~8 | ~6.7 |\n", "| D `accumulate` | ~10 | ~7 |\n", "\n", "All four are $O(n)$, so the gaps are **constant factors**:\n", "- **A is fastest with no zeros** because `count`, `math.prod` and one comprehension are mostly\n", " C-level work. With one zero it does extra passes and C catches up. Fast, but it skips the\n", " follow-up, which was the point.\n", "- **B is slowest:** two extra $n$-sized lists plus three Python loops (two index loops and the\n", " `zip`). C does the same work with no extra arrays.\n", "- **D isn't a free win:** `accumulate`/`map` run in C, but it builds three $n$-sized lists\n", " (prefix, suffix, the `suffix[:-1]` slice) and every multiplication still creates a Python int,\n", " so it ends up level with C. \"Use the C builtin\" only pays off when it removes a lot of Python\n", " bytecode; here C's loop is already very simple." ] }, { "cell_type": "code", "id": "aa08e5d35812", "metadata": {}, "source": [ "import random\n", "\n", "random.seed(0)\n", "no_zero = [random.choice([1, -1]) for _ in range(100_000)]\n", "for i in random.sample(range(100_000), 20):\n", " no_zero[i] = 2\n", "one_zero = list(no_zero)\n", "one_zero[50_000] = 0\n", "\n", "for label, nums in [(\"no zero\", no_zero), (\"one zero\", one_zero)]:\n", " print(f\"--- {label}\")\n", " for fn in APPROACHES:\n", " print(f\"{fn.__name__:32s}\", end=\" \")\n", " %timeit fn(nums)" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "f1e301569e3c", "metadata": {}, "source": [ "## 6. Takeaways\n", "\n", "- **Pattern:** \"combine everything **except** index `i`\" (or \"everything left of `i`\" /\n", " \"everything right of `i`\") → **prefix × suffix**: one pass left-to-right, one pass\n", " right-to-left. Store one direction in the output and keep the other as a running variable for\n", " $O(1)$ extra space. Same shape as prefix **sums**, just with `*` instead of `+`.\n", "- **Mistakes I made:**\n", " - Reached for **division** to \"undo\" one element. Inverting an operation needs special cases\n", " (here: zeros, and exact vs floor division with negatives) and is often banned or impossible\n", " (`max`, `gcd`, overflow in fixed-width ints). Prefix/suffix needs no inverse at all.\n", " - Didn't treat the follow-up as the real question: \"$O(n)$ without division\" was the point of\n", " the problem.\n", " - Small hygiene: built `result` before an early return that didn't need it, checked the same\n", " condition twice (`zero_count` and `prod != 0`), and reused `num` inside a comprehension.\n", "- **Related problems:** Range Sum Query – Immutable (#303, prefix sums), Trapping Rain Water\n", " (#42, prefix max from the left vs suffix max from the right), Maximum Product Subarray (#152,\n", " running products with negatives), Subarray Sum Equals K (#560, prefix sums + hash map),\n", " Find Pivot Index (#724, left sum vs right sum)." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }