{ "cells": [ { "cell_type": "markdown", "id": "95ec83562988", "metadata": {}, "source": [ "# Contains Duplicate\n", "\n", "| Field | Value |\n", "|------------|-----------------------------------------|\n", "| Source | [link](https://leetcode.com/problems/contains-duplicate/) |\n", "| Difficulty | Easy |\n", "| Topics | `array`, `hash set`, `sorting` |\n", "| Date | 2026-10-07 |\n", "| Status | Solved |" ] }, { "cell_type": "markdown", "id": "dbfd2e8283d8", "metadata": {}, "source": [ "## 1. Problem\n", "\n", "> Given an integer array `nums`, return `true` if any value appears more than once\n", "> in the array, otherwise return `false`.\n", "\n", "**Example 1**\n", "```\n", "Input: nums = [1, 2, 3, 3]\n", "Output: true\n", "```\n", "\n", "**Example 2**\n", "```\n", "Input: nums = [1, 2, 3, 4]\n", "Output: false\n", "```\n", "\n", "**Constraints**\n", "- `0 <= len(nums) <= 10^5`\n", "- `-10^9 <= nums[i] <= 10^9`" ] }, { "cell_type": "markdown", "id": "de4a66da7f9b", "metadata": {}, "source": [ "## 2. Thinking\n", "\n", "- **Brute force idea:** for each element, scan the rest of the list for the same value → $O(n^2)$.\n", " With $n = 10^5$ that is ~$5 \\cdot 10^9$ comparisons — too slow.\n", "- **Key insight:** the question is really *\"have I seen this value before?\"*. A `set`\n", " answers that in $O(1)$ average time, so one pass is enough.\n", "- **Edge cases to remember:** empty list, single element, duplicates at the very end,\n", " negative numbers, large values." ] }, { "cell_type": "code", "id": "b5ee68ca9cb4", "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": "5b6881144d8a", "metadata": {}, "source": [ "## 3. Solution\n", "\n", "### Approach A — my first solution (pop + `in`)\n", "Pop the first element and check whether it still appears in the remaining list.\n", "\n", "**Complexity:** Time $O(n^2)$ · Space $O(1)$\n", "\n", "Why it's slow — two hidden linear costs per loop:\n", "- `nums.pop(0)` is $O(n)$: removing the front of a Python list shifts every other element left.\n", " (`pop()` from the *end* is $O(1)$.)\n", "- `temp in nums` is $O(n)$: `in` on a **list** is a linear scan. (`in` on a **set** is $O(1)$.)\n", "\n", "It also **empties the caller's list** as a side effect." ] }, { "cell_type": "code", "id": "da2b9011798c", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "def has_duplicate_mine(nums: list[int]) -> bool:\n", " while nums:\n", " temp = nums.pop(0) # O(n): shifts the rest of the list\n", " if temp in nums: # O(n): linear scan of a list\n", " return True\n", " return False" ] }, { "cell_type": "markdown", "id": "b6146d7efd6d", "metadata": {}, "source": [ "### Approach B — sort, then compare neighbours\n", "After sorting, equal values sit next to each other.\n", "\n", "**Complexity:** Time $O(n \\log n)$ · Space $O(n)$ for `sorted` (or $O(1)$ extra with in-place `nums.sort()`, which mutates the input).\n", "Useful when memory is tight." ] }, { "cell_type": "code", "id": "c9082297a87e", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "def has_duplicate_sort(nums: list[int]) -> bool:\n", " s = sorted(nums)\n", " for i in range(1, len(s)):\n", " if s[i] == s[i - 1]:\n", " return True\n", " return False" ] }, { "cell_type": "markdown", "id": "4e44c0b16088", "metadata": {}, "source": [ "### Approach C — hash set, one pass ✅ best practice\n", "Keep a set of values seen so far; return `True` the moment one repeats.\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(n)$. Stops early on the first duplicate." ] }, { "cell_type": "code", "id": "bfafbe6150ef", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "def has_duplicate(nums: list[int]) -> bool:\n", " seen = set()\n", " for x in nums:\n", " if x in seen:\n", " return True\n", " seen.add(x)\n", " return False" ] }, { "cell_type": "markdown", "id": "721b756e96be", "metadata": {}, "source": [ "### Approach D — Pythonic one-liner\n", "A set drops duplicates, so if it's smaller than the list, something repeated.\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(n)$. Short and fast in practice (the loop runs in C),\n", "but it always builds the whole set — no early exit." ] }, { "cell_type": "code", "id": "0d09c0ed1d7c", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "def has_duplicate_len(nums: list[int]) -> bool:\n", " return len(set(nums)) != len(nums)" ] }, { "cell_type": "markdown", "id": "31328da6b7b6", "metadata": {}, "source": [ "## 4. Tests\n", "\n", "All four implementations run against the same cases. Each test passes a **copy**\n", "(`list(nums)`) because Approach A empties the list it's given." ] }, { "cell_type": "code", "id": "411e93e62146", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "%%ipytest -q\n", "\n", "CASES = [\n", " ([1, 2, 3, 3], True),\n", " ([1, 2, 3, 4], False),\n", " ([], False), # empty\n", " ([7], False), # single element\n", " ([5, 5], True),\n", " ([-1, 0, 1, -1], True), # negatives\n", " ([10**9, -10**9, 10**9], True), # extreme values\n", " ([1, 2, 3, 4, 5, 1], True), # duplicate far apart\n", "]\n", "\n", "@pytest.mark.parametrize(\"fn\", [has_duplicate_mine, has_duplicate_sort, has_duplicate, has_duplicate_len])\n", "@pytest.mark.parametrize(\"nums, expected\", CASES)\n", "def test_has_duplicate(fn, nums, expected):\n", " assert fn(list(nums)) == expected" ] }, { "cell_type": "markdown", "id": "466483742642", "metadata": {}, "source": [ "## 5. Scratch / Experiments\n", "\n", "Timing on a worst case: no duplicates, so every approach has to look at everything.\n", "(Approach A is limited to 10,000 elements — at $10^5$ it would take far longer.)" ] }, { "cell_type": "code", "id": "940111ed8cf7", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "big = list(range(10_000))\n", "%timeit -n 1 -r 1 has_duplicate_mine(list(big))\n", "%timeit has_duplicate_sort(big)\n", "%timeit has_duplicate(big)\n", "%timeit has_duplicate_len(big)" ] }, { "cell_type": "markdown", "id": "7e2b614be59b", "metadata": {}, "source": [ "## 6. Takeaways\n", "\n", "- **Pattern:** \"have I seen this before?\" / uniqueness / counting → **hash set** (or `dict` /\n", " `collections.Counter` when you need counts or indices). Trade $O(n)$ memory for $O(1)$ lookups.\n", " Fallback when memory matters: **sort first**, then duplicates are neighbours.\n", "- **Mistakes I made:**\n", " - `list.pop(0)` is $O(n)$ — use `collections.deque.popleft()` if you really need to pop from the front.\n", " - `x in some_list` is $O(n)$; `x in some_set` is $O(1)$. Pick the container based on the operation.\n", " - Mutated the input list — avoid side effects unless the problem allows it.\n", "- **Related problems:** Two Sum (#1, same \"seen\" idea with a dict), Contains Duplicate II (#219,\n", " sliding-window set), Valid Anagram (#242, counting), Longest Consecutive Sequence (#128, set lookups),\n", " Find the Duplicate Number (#287, $O(1)$ space twist)." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }