{ "cells": [ { "cell_type": "markdown", "id": "ca9ab6f2c6ad", "metadata": {}, "source": [ "# Longest Consecutive Sequence\n", "\n", "| Field | Value |\n", "|------------|-----------------------------------------|\n", "| Source | [link](https://leetcode.com/problems/longest-consecutive-sequence/) |\n", "| Difficulty | Medium |\n", "| Topics | `array`, `hash set`, `union find` |\n", "| Date | 2026-10-14 |\n", "| Status | Solved |" ] }, { "cell_type": "markdown", "id": "4cf42bf10c8b", "metadata": {}, "source": [ "## 1. Problem\n", "\n", "> Given an array of integers `nums`, return the length of the longest consecutive sequence of\n", "> elements that can be formed. A consecutive sequence is a sequence of elements in which each\n", "> element is exactly 1 greater than the previous element. The elements do not have to be\n", "> consecutive in the original array.\n", ">\n", "> You must write an algorithm that runs in $O(n)$ time.\n", "\n", "**Example 1**\n", "```\n", "Input: nums = [2, 20, 4, 10, 3, 4, 5]\n", "Output: 4 # [2, 3, 4, 5]\n", "```\n", "\n", "**Example 2**\n", "```\n", "Input: nums = [0, 3, 2, 5, 4, 6, 1, 1]\n", "Output: 7 # [0, 1, 2, 3, 4, 5, 6]\n", "```\n", "\n", "**Constraints**\n", "- `0 <= len(nums) <= 10^5`\n", "- `-10^9 <= nums[i] <= 10^9`" ] }, { "cell_type": "markdown", "id": "f94ae0efde03", "metadata": {}, "source": [ "## 2. Thinking\n", "\n", "- **Brute force idea:** treat every element as the start of a sequence and count up with\n", " `x + 1 in nums`. With a list lookup that's $O(n^3)$; with a set it's still $O(n^2)$ because\n", " every element of a long run re-walks the rest of the run.\n", "- **Sorting idea:** sort, then scan once counting runs (skip duplicates, reset on a gap):\n", " $O(n \\log n)$. Correct and simple, but breaks the $O(n)$ requirement.\n", "- **Key insight:** only walk from the **start of a sequence**: `x` is a start iff `x - 1` is\n", " **not** in the set. Then each number is visited once by the `for` loop and at most once by a\n", " `while` walk, so the total work is $O(n)$ (amortized, even though there's a nested loop).\n", "- **Loop over the set, not the list.** With duplicates of a start value\n", " (`[0, 0, 0, ..., 0, 1, 2, ..., m]`) looping over `nums` re-walks the same run once per copy:\n", " $O(n^2)$.\n", "- **Edge cases to remember:** empty array → `0`; duplicates (`[1, 1]` → 1, they don't extend a\n", " run); negatives and runs crossing 0; all elements isolated → 1; values near $\\pm 10^9$\n", " (fine in Python, `x + 1` can't overflow)." ] }, { "cell_type": "code", "id": "23b342b34086", "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": "6b923f0efa3e", "metadata": {}, "source": [ "## 3. Solution\n", "\n", "### Approach A — my version (hash set, walk from sequence starts)\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(n)$. This already **is** the optimal algorithm, and it\n", "loops over the set, so duplicates can't make it quadratic. Small things only:\n", "1. `n + 1 in nums_set` skips singletons before any walking. It costs an extra lookup per start\n", " but saves the `while` setup and the `max()` call, and on sparse data (most numbers isolated)\n", " that makes mine the **fastest** version (see section 5). The price is the `len == 0` guard\n", " and `counter = 1`.\n", "2. `start` is really the **current end** of the run, and `temp_counter` duplicates what\n", " `start - n + 1` already tells you. One variable is enough.\n", "\n", "The code is unchanged except for the signature and comments." ] }, { "cell_type": "code", "id": "7b08c6fa7bea", "metadata": {}, "source": [ "def longest_consecutive_mine(nums: list[int]) -> int:\n", " if len(nums) == 0: # needed because counter starts at 1\n", " return 0\n", " nums_set = set(nums)\n", " counter = 1\n", "\n", " for n in nums_set: # good: set, not list (no duplicate re-walks)\n", " if n - 1 not in nums_set and n + 1 in nums_set: # skips singletons cheaply (a speed win)\n", " start = n # really the current end of the run\n", " temp_counter = 1\n", " while start + 1 in nums_set:\n", " temp_counter += 1\n", " start += 1\n", " counter = max(counter, temp_counter)\n", " return counter" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "f30bd5c7e0bf", "metadata": {}, "source": [ "### Approach B — sort and scan\n", "\n", "**Complexity:** Time $O(n \\log n)$ · Space $O(n)$ for the sorted copy.\n", "Sort, then count runs: same value → skip, `+1` → extend, anything else → reset. Doesn't meet the\n", "$O(n)$ requirement, but it's the natural first answer and useful when memory for a set is tight\n", "(sorting in place needs no extra hash table)." ] }, { "cell_type": "code", "id": "b2fd5cf116a9", "metadata": {}, "source": [ "def longest_consecutive_sort(nums: list[int]) -> int:\n", " if not nums:\n", " return 0\n", " nums = sorted(nums) # copy: don't mutate the caller's list\n", " longest = current = 1\n", " for prev, x in zip(nums, nums[1:]):\n", " if x == prev:\n", " continue # duplicate: neither extends nor breaks the run\n", " if x == prev + 1:\n", " current += 1\n", " longest = max(longest, current)\n", " else:\n", " current = 1\n", " return longest" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "ca0e210cb9f1", "metadata": {}, "source": [ "### Approach C — hash set, walk only from starts ✅ best practice\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(n)$.\n", "Approach A, tidied: no special cases, one walking variable. The `if x - 1 not in num_set` line\n", "is the whole trick; it guarantees each run is walked exactly once." ] }, { "cell_type": "code", "id": "99aca6b74163", "metadata": {}, "source": [ "def longest_consecutive(nums: list[int]) -> int:\n", " num_set = set(nums)\n", " longest = 0\n", " for x in num_set: # the set, so duplicates don't cause re-walks\n", " if x - 1 not in num_set: # x starts a run\n", " end = x\n", " while end + 1 in num_set:\n", " end += 1\n", " longest = max(longest, end - x + 1)\n", " return longest" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "cc9026278678", "metadata": {}, "source": [ "### Approach D — hash map of run lengths at the boundaries (one pass)\n", "\n", "**Complexity:** Time $O(n)$ · Space $O(n)$.\n", "For each new `x`, look up the run lengths ending at `x - 1` (`left`) and starting at `x + 1`\n", "(`right`). The merged run has length `left + right + 1`; store it at `x` and at the two new\n", "boundaries `x - left` and `x + right`. Only boundaries need to be correct, so it's $O(1)$ per\n", "element. Same idea as union-find on consecutive numbers; useful when numbers arrive as a stream." ] }, { "cell_type": "code", "id": "3db434fbb679", "metadata": {}, "source": [ "def longest_consecutive_boundary(nums: list[int]) -> int:\n", " run = {} # x -> length of the run x belongs to (only reliable at run boundaries)\n", " longest = 0\n", " for x in nums:\n", " if x in run:\n", " continue # duplicate\n", " left = run.get(x - 1, 0)\n", " right = run.get(x + 1, 0)\n", " length = left + right + 1\n", " run[x] = run[x - left] = run[x + right] = length\n", " longest = max(longest, length)\n", " return longest" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "176265ba0bc2", "metadata": {}, "source": [ "## 4. Tests\n", "\n", "Every approach runs against every case. Approach B sorts a copy, so no input is mutated." ] }, { "cell_type": "code", "id": "81dad1135573", "metadata": {}, "source": [ "%%ipytest -q\n", "\n", "APPROACHES = [longest_consecutive_mine, longest_consecutive_sort, longest_consecutive, longest_consecutive_boundary]\n", "\n", "CASES = [\n", " ([2, 20, 4, 10, 3, 4, 5], 4),\n", " ([0, 3, 2, 5, 4, 6, 1, 1], 7),\n", " ([], 0), # empty\n", " ([7], 1), # single element\n", " ([1, 1, 1], 1), # only duplicates\n", " ([10, 30, 20], 1), # all isolated\n", " ([-2, -1, 0, 1, 2], 5), # negatives, run crosses 0\n", " ([5, 4, 3, 2, 1], 5), # descending input\n", " ([1, 3, 2, 1, 2, 3, 4], 4), # duplicates inside a run\n", " ([1, 2, 3, 100, 101, 102, 103], 4), # two runs, the later one is longer\n", " ([-10**9, 10**9, 10**9 - 1], 2), # extreme values\n", " ([1, 3, 2, 10, 12, 11, 13], 4), # x fills a gap, merging runs on both sides (D)\n", " (list(range(100_000)), 100_000), # max size, one run\n", "]\n", "\n", "@pytest.mark.parametrize(\"fn\", APPROACHES)\n", "@pytest.mark.parametrize(\"nums, expected\", CASES)\n", "def test_longest_consecutive(fn, nums, expected):\n", " assert fn(nums) == expected" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "a20a9233b397", "metadata": {}, "source": [ "## 5. Scratch / Experiments\n", "\n", "Two inputs at the max size $n = 10^5$:\n", "- **random:** values from the full range $\\pm 10^9$, so almost every run has length 1;\n", "- **one run:** `range(n)` shuffled, so one run of length $n$ (the `while` walk does all the work).\n", "\n", "Measured on my machine:\n", "\n", "| approach | random ($\\pm 10^9$) | one run |\n", "|---|---|---|\n", "| A, mine (set + singleton filter) | **8.9 ms** | 10.1 ms |\n", "| B, sort | 12.8 ms | 15.7 ms |\n", "| C, set (best practice) | 12.1 ms | **9.5 ms** |\n", "| D, boundary map | 22.0 ms | 22.2 ms |\n", "\n", "- **A beats C on random data.** Almost every number is a run of length 1. C still calls\n", " `max()` and computes `end - x + 1` for each one; A's `n + 1 in nums_set` check drops them first.\n", " A Python function call costs more than a set lookup, so the filter pays off. On one long run\n", " there's only one start, so the filter does nothing and the two are about even.\n", "- **Sorting (B) is close** despite $O(n \\log n)$: `sorted` is Timsort in C and\n", " $\\log_2 10^5 \\approx 17$ is small. Big-O says how it grows, not which wins at this size.\n", "- **D is the slowest**, despite being one pass: it does ~4 dict operations per element and\n", " allocates a dict entry for each one.\n", "- **The trap:** looping over the list is ~800× slower (122 ms vs 155 μs) on just 4000\n", " elements, because the run of 2000 is re-walked once for each of the 2000 copies of `0`.\n", "\n", "The last block shows the trap from section 2: looping over **`nums`** instead of the set, with many\n", "copies of a run's start. Shrunk to $m = 2000$ copies + a run of 2000 because it's quadratic." ] }, { "cell_type": "code", "id": "7810bbefee9d", "metadata": {}, "source": [ "import random\n", "\n", "random.seed(0)\n", "n = 100_000\n", "random_nums = [random.randint(-10**9, 10**9) for _ in range(n)]\n", "one_run = list(range(n))\n", "random.shuffle(one_run)\n", "\n", "for label, data in [(\"random\", random_nums), (\"one run\", one_run)]:\n", " print(f\"--- {label}\")\n", " for fn in APPROACHES:\n", " print(f\"{fn.__name__:30s}\", end=\" \")\n", " %timeit -n 5 -r 3 fn(data)" ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "id": "936495d9d22e", "metadata": {}, "source": [ "def longest_consecutive_loop_list(nums: list[int]) -> int:\n", " num_set = set(nums)\n", " longest = 0\n", " for x in nums: # SLOW: list, so each duplicate start re-walks its run\n", " if x - 1 not in num_set:\n", " end = x\n", " while end + 1 in num_set:\n", " end += 1\n", " longest = max(longest, end - x + 1)\n", " return longest\n", "\n", "m = 2000\n", "trap = [0] * m + list(range(m)) # m copies of the start 0, run length m\n", "for fn in (longest_consecutive, longest_consecutive_loop_list):\n", " print(f\"{fn.__name__:30s}\", end=\" \")\n", " %timeit -n 3 -r 3 fn(trap)" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "1e4cdc18f526", "metadata": {}, "source": [ "## 6. Takeaways\n", "\n", "- **Pattern:** \"longest run of consecutive values in $O(n)$, original order doesn't matter\" →\n", " **put everything in a hash set and only start counting at run starts** (`x - 1 not in set`).\n", " A nested `while` is still $O(n)$ total when each element is walked at most once: argue it by\n", " **amortization**, not by counting loop depth.\n", "- **Mistakes I made:**\n", " - None in correctness or Big-O: my solution was already the optimal approach and correctly\n", " looped over the set.\n", " - The `n + 1 in nums_set` filter is a real optimization (it skips `max()` for every isolated\n", " number), but it forced a `len == 0` guard and `counter = 1`. In an interview, write the\n", " simple version (`longest = 0`, no guard) first; add the filter as a micro-optimization.\n", " - Two variables (`start`, `temp_counter`) tracked the same thing. Keep one (`end`) and compute\n", " the length as `end - x + 1`.\n", " - Remember **why** iterating the set matters: over the list, duplicates of a start value make\n", " it $O(n^2)$.\n", "- **Related problems:** Contains Duplicate (#217, the same \"hash set for $O(1)$ membership\" step),\n", " Binary Tree Longest Consecutive Sequence (#298, the same \"+1 chain\" on a tree), Number of\n", " Islands (#200) / Graph Valid Tree (#261) (union-find, the idea behind Approach D), Missing\n", " Number (#268) and First Missing Positive (#41) (reasoning about which values are present)." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }