{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6af1e630dc26",
   "metadata": {},
   "source": [
    "# Two Sum\n",
    "\n",
    "| Field      | Value                                                    |\n",
    "|------------|----------------------------------------------------------|\n",
    "| Source     | [LeetCode #1](https://leetcode.com/problems/two-sum/)    |\n",
    "| Difficulty | Easy                                                     |\n",
    "| Topics     | `array`, `hash map`                                      |\n",
    "| Date       | 2026-10-05                                               |\n",
    "| Status     | Solved                                                   |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fb87c8df862",
   "metadata": {},
   "source": [
    "## 1. Problem\n",
    "\n",
    "> Given an array of integers `nums` and an integer `target`, return the *indices*\n",
    "> of the two numbers that add up to `target`. Exactly one solution exists, and you\n",
    "> may not use the same element twice. The answer can be in any order.\n",
    "\n",
    "**Example 1**\n",
    "```\n",
    "Input:  nums = [2, 7, 11, 15], target = 9\n",
    "Output: [0, 1]\n",
    "```\n",
    "\n",
    "**Example 2**\n",
    "```\n",
    "Input:  nums = [3, 2, 4], target = 6\n",
    "Output: [1, 2]\n",
    "```\n",
    "\n",
    "**Example 3**\n",
    "```\n",
    "Input:  nums = [3, 3], target = 6\n",
    "Output: [0, 1]\n",
    "```\n",
    "\n",
    "**Constraints**\n",
    "- `2 <= len(nums) <= 10^4`\n",
    "- `-10^9 <= nums[i] <= 10^9`, `-10^9 <= target <= 10^9`\n",
    "- Exactly one valid answer exists"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f6b6cc6bb1b",
   "metadata": {},
   "source": [
    "## 2. Thinking\n",
    "\n",
    "- **Brute force idea:** check every pair → $O(n^2)$.\n",
    "- **Key insight:** for each `x`, I need `target - x`. Remembering the numbers seen so far\n",
    "  answers \"have I seen it?\" in $O(1)$. Because the answer is **indices**, remember\n",
    "  *where* each number was too: a dict of *value → index*.\n",
    "- **Edge cases to remember:** duplicates like `[3, 3]`, negative numbers, zeros\n",
    "  (`[0, 4, 0]`, target `0`), the pair being the last two elements."
   ]
  },
  {
   "cell_type": "code",
   "id": "59c0959a44fc",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2026-10-07T21:09:34.464391Z",
     "start_time": "2026-10-07T21:09:34.358790600Z"
    }
   },
   "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()"
   ],
   "outputs": [],
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "id": "efe11c7b1e85",
   "metadata": {},
   "source": [
    "## 3. Solution\n",
    "\n",
    "### Approach A — my solution: hash set + `list.index`\n",
    "Store seen values in a set; when the complement is found, look up its position with `nums.index`.\n",
    "\n",
    "**Complexity:** Time $O(n)$ · Space $O(n)$ — the same Big-O as the best answer.\n",
    "\n",
    "It is correct, including duplicates: the set only holds *earlier* elements, and `nums.index`\n",
    "returns the **first** occurrence, which is always before `index`. The only cost is that a set\n",
    "throws the position away, so `nums.index` has to scan the list again (once, at the end) to find it."
   ]
  },
  {
   "cell_type": "code",
   "id": "6efb738f008d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2026-10-07T21:09:34.474966300Z",
     "start_time": "2026-10-07T21:09:34.466976100Z"
    }
   },
   "source": [
    "def two_sum_mine(nums: list[int], target: int) -> list[int]:\n",
    "    seen = set()\n",
    "    for index, num in enumerate(nums):\n",
    "        if target - num in seen:\n",
    "            return [nums.index(target - num), index]  # O(n) second scan: the set lost the index\n",
    "        seen.add(num)\n",
    "    return []"
   ],
   "outputs": [],
   "execution_count": 2
  },
  {
   "cell_type": "markdown",
   "id": "8568711d9f8b",
   "metadata": {},
   "source": [
    "### Approach B — brute force\n",
    "**Complexity:** Time $O(n^2)$ · Space $O(1)$"
   ]
  },
  {
   "cell_type": "code",
   "id": "acc76764096d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2026-10-07T21:09:34.483423900Z",
     "start_time": "2026-10-07T21:09:34.476967500Z"
    }
   },
   "source": [
    "def two_sum_brute(nums: list[int], target: int) -> list[int]:\n",
    "    for i in range(len(nums)):\n",
    "        for j in range(i + 1, len(nums)):\n",
    "            if nums[i] + nums[j] == target:\n",
    "                return [i, j]\n",
    "    return []"
   ],
   "outputs": [],
   "execution_count": 3
  },
  {
   "cell_type": "markdown",
   "id": "e49965659b43",
   "metadata": {},
   "source": [
    "### Approach C — one-pass hash map ✅ best practice\n",
    "Same idea as Approach A, but store **value → index** in a dict, so the answer's index is\n",
    "already there when the complement is found. No second scan.\n",
    "\n",
    "**Complexity:** Time $O(n)$ · Space $O(n)$"
   ]
  },
  {
   "cell_type": "code",
   "id": "782de0263bcd",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2026-10-07T21:09:34.491598300Z",
     "start_time": "2026-10-07T21:09:34.485425200Z"
    }
   },
   "source": [
    "def two_sum(nums: list[int], target: int) -> list[int]:\n",
    "    seen = {}  # value -> index\n",
    "    for i, x in enumerate(nums):\n",
    "        if target - x in seen:\n",
    "            return [seen[target - x], i]\n",
    "        seen[x] = i\n",
    "    return []"
   ],
   "outputs": [],
   "execution_count": 4
  },
  {
   "cell_type": "markdown",
   "id": "11a6e23e0bdf",
   "metadata": {},
   "source": [
    "## 4. Tests\n",
    "\n",
    "All three implementations are tested against the same cases by parametrizing over the function too."
   ]
  },
  {
   "cell_type": "code",
   "id": "76ccb6e2d13e",
   "metadata": {},
   "source": [
    "%%ipytest -q\n",
    "\n",
    "CASES = [\n",
    "    ([2, 7, 11, 15], 9, [0, 1]),\n",
    "    ([3, 2, 4], 6, [1, 2]),\n",
    "    ([3, 3], 6, [0, 1]),             # duplicates\n",
    "    ([-1, -2, -3, -4], -7, [2, 3]),  # negatives\n",
    "    ([0, 4, 0], 0, [0, 2]),          # zeros: must not pair an element with itself\n",
    "    ([1, 5, 1, 5], 10, [1, 3]),      # repeated value, answer uses the 2nd copy\n",
    "    ([5, 1, 2, 9, 11], 20, [3, 4]),  # pair at the very end\n",
    "]\n",
    "\n",
    "@pytest.mark.parametrize(\"fn\", [two_sum_mine, two_sum_brute, two_sum])\n",
    "@pytest.mark.parametrize(\"nums, target, expected\", CASES)\n",
    "def test_two_sum(fn, nums, target, expected):\n",
    "    assert fn(nums, target) == expected"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "f61d92e97bb9",
   "metadata": {},
   "source": [
    "## 5. Scratch / Experiments\n",
    "\n",
    "Worst case at the max size ($10^4$): the pair is the last two elements, so every approach\n",
    "has to look at everything — and in Approach A, `nums.index` scans almost the whole list\n",
    "again. Brute force runs only once because it takes seconds."
   ]
  },
  {
   "cell_type": "code",
   "id": "74b62d7abf11",
   "metadata": {},
   "source": [
    "big = list(range(10_000))\n",
    "target = big[-1] + big[-2]\n",
    "%timeit -n 1 -r 1 two_sum_brute(big, target)\n",
    "%timeit two_sum_mine(big, target)\n",
    "%timeit two_sum(big, target)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "938f2c759b43",
   "metadata": {},
   "source": [
    "## 6. Takeaways\n",
    "\n",
    "- **Pattern:** \"find a complement\" → store what you've seen in a hash table.\n",
    "  If the answer needs **positions**, store `value → index` in a **dict**, not just values in a set.\n",
    "- **Mistakes I made:**\n",
    "  - Used a set, which forgets *where* each value was, so I had to search again with `nums.index`\n",
    "    (an extra $O(n)$ scan). Ask \"what do I need back at the end?\" and store that.\n",
    "  - It only works because `nums.index` returns the *first* match and the set holds only earlier\n",
    "    elements — correct, but subtle. The dict version doesn't need that reasoning.\n",
    "  - Watch out for inserting `x` into `seen` *before* checking: that matches an element with itself\n",
    "    (e.g. `[3, 2, 4]`, target `6`).\n",
    "- **Related problems:** Contains Duplicate (#217, \"seen\" with a set), Two Sum II (#167, sorted input\n",
    "  → two pointers, $O(1)$ space), 3Sum (#15, sort + two pointers), Two Sum IV (#653, BST)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}