{"title":"Python Crash Course for DSA","description":"","content":"This chapter is a focused crash course on the Python features that come up repeatedly in DSA and preparing for coding interviews. Instead of covering the entire language, we will concentrate only on the parts that matter for solving problems efficiently in interviews.\n\n---\n\n# Common Imports\n\nOn LeetCode, most imports are available automatically. But when writing Python locally or on some interview platforms, you need to know what to import. Here are the imports that cover 95% of DSA problems:\n\n\n```python\nfrom collections import defaultdict, Counter, deque, OrderedDict\nfrom heapq import heappush, heappop, heapify, nlargest, nsmallest\nfrom bisect import bisect_left, bisect_right, insort\nfrom functools import lru_cache, cache, cmp_to_key\nfrom itertools import combinations, permutations, product, accumulate\nfrom math import inf, ceil, floor, gcd, log2, sqrt, isqrt\nfrom typing import List, Optional, Dict, Set, Tuple\nimport sys\n```\n\n\nEach of these modules serves a specific purpose in DSA:\n\n\n| Module | What It Provides | DSA Use Case |\n|--------|-----------------|--------------|\n| `collections` | `defaultdict`, `Counter`, `deque`, `OrderedDict` | Frequency counting, BFS queues, adjacency lists |\n| `heapq` | Min-heap operations | Top-K elements, Dijkstra, merge-K-sorted |\n| `bisect` | Binary search on sorted lists | Insertion point, sorted container operations |\n| `functools` | `lru_cache`, `cache`, `cmp_to_key` | DP memoization, custom sorting |\n| `itertools` | `combinations`, `permutations`, `product`, `accumulate` | Generating subsets, prefix sums |\n| `math` | `inf`, `gcd`, `isqrt`, `ceil`, `floor` | Sentinel values, number theory |\n| `typing` | Type hints | Code clarity on LeetCode |\n| `sys` | `setrecursionlimit` | Deep recursion for DFS/trees |\n\n\nOne line is worth adding up front:\n\n\n```python\nsys.setrecursionlimit(10**6)\n```\n\n\nPython's default recursion limit is 1000. Without this line, DFS on a graph with 100,000 nodes or a skewed binary tree raises a `RecursionError`. We will cover recursion in detail later.\n\nThere is also one third-party library available on LeetCode that provides sorted container data structures:\n\n\n```python\nfrom sortedcontainers import SortedList, SortedDict, SortedSet\n```\n\n\nThis is not part of Python's standard library, but it is available on LeetCode and many interview platforms. We will cover it in the Sorted Containers section.\n\n---\n\n# Variables, Types, and Python's Integer Advantage\n\nPython is a dynamically typed language. You do not declare types, you just assign values. The interpreter figures out the type at runtime:\n\n\n```python\ncount = 0 # int\nratio = 3.14 # float\nname = \"hello\" # str\nfound = True # bool\nnothing = None # NoneType\n```\n\n\nFor DSA, a small set of types covers most problems:\n\n\n| Type | Example | DSA Use Case |\n|------|---------|--------------|\n| `int` | `42`, `2**100` | Array indices, counters, any integer (no overflow!) |\n| `float` | `3.14`, `float('inf')` | Sentinel values, rarely used otherwise |\n| `bool` | `True`, `False` | Visited arrays, flags |\n| `str` | `\"hello\"` | Immutable character sequences |\n| `None` | `None` | Null equivalent, tree/linked list terminators |\n\n\nPython integers have arbitrary precision, which is a big advantage for DSA. Python integers never overflow.\n\n\n```python\n# This works perfectly in Python\nresult = 2 ** 1000\n# 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376\n```\n\n\nThis means you never need to worry about integer overflow in most DSA problems. The safe binary search midpoint formula `left + (right - left) // 2` is still good practice for clarity and habit, but technically unnecessary in Python because `(left + right) // 2` will never overflow.\n\n### Floor Division vs True Division\n\nThis distinction matters:\n\n\n```python\n7 / 2 # 3.5 (true division, returns float)\n7 // 2 # 3 (floor division, returns int)\n-7 // 2 # -4 (floors toward negative infinity, NOT toward zero!)\n```\n\n\nThat last line is important. In Python, `-7 // 2` gives `-4` because floor division rounds toward negative infinity, not toward zero. If you need truncation toward zero, use `int(-7 / 2)` or `math.trunc(-7 / 2)`.\n\n### The Ternary Expression\n\nPython writes conditional expressions inline using `if`/`else`:\n\n\n```python\nresult = a if a > b else b # Same as max(a, b)\nlabel = \"even\" if n % 2 == 0 else \"odd\"\n```\n\n\n### Multiple Assignment and Swap\n\nPython supports multiple assignment, which is handy for DSA:\n\n\n```python\n# Multiple assignment\na, b = 0, 1\nleft, right = 0, len(nums) - 1\n\n# Swap without a temp variable\na, b = b, a\n\n# This works because Python evaluates the right side fully before assignment\n# In Fibonacci:\na, b = b, a + b # Both update simultaneously\n```\n\n\nThe swap trick is particularly useful in partition-based algorithms and two-pointer problems where you constantly need to swap elements.\n\n### Type Hints\n\nPython supports optional type hints that make your code clearer on LeetCode:\n\n\n```python\ndef twoSum(nums: List[int], target: int) -> List[int]:\n ...\n```\n\n\nType hints have no runtime effect. They are purely for readability. LeetCode uses them in function signatures, so they appear throughout this course.\n\n### Booleans Are Integers\n\nA quirk worth knowing: `bool` is a subclass of `int` in Python. `True` is `1` and `False` is `0`:\n\n\n```python\nTrue + True # 2\nsum([True, False, True, True]) # 3 (counts True values)\n```\n\n\nThis is useful for counting conditions:\n\n\n```python\n# Count elements greater than threshold\ncount = sum(1 for x in nums if x > threshold)\n# Or equivalently:\ncount = sum(x > threshold for x in nums)\n```\n\n\n---\n\n# Operators and Control Flow\n\nMost operators in Python work as you would expect, but a few deserve special attention for DSA.\n\n### Modular Arithmetic\n\nThe `%` operator in Python always returns a result with the same sign as the **divisor** (the right operand). This is convenient for DSA:\n\n\n```python\n-7 % 3 # 2 (Python: always non-negative when divisor is positive)\n```\n\n\nThis means you do not need the `((n % m) + m) % m` trick to force a positive modulo result.\n\nMany problems ask you to return the result \"modulo 10^9 + 7\":\n\n\n```python\nMOD = 10**9 + 7\n\n# Apply modulo during computation, not just at the end\nresult = 0\nfor val in values:\n result = (result + val) % MOD\n```\n\n\n### Bitwise Operators\n\nBitwise operations come up in several DSA patterns:\n\n\n```python\n# XOR trick: find the number that appears once (all others appear twice)\n# nums = [4, 1, 2, 1, 2]\nsingle = 0\nfor num in nums:\n single ^= num # XOR cancels out duplicates\n# single = 4\n```\n\n\nKey bitwise operators:\n\n\n| Operator | Symbol | DSA Use |\n|----------|--------|---------|\n| AND | `&` | Masking, checking if bit is set: `(n & (1 << i)) != 0` |\n| OR | `\\|` | Setting bits: `n \\| (1 << i)` |\n| XOR | `^` | Finding unique elements, toggling bits |\n| NOT | `~` | Bit inversion (`~n` equals `-(n+1)` in Python) |\n| Left shift | `<<` | Multiply by powers of 2: `1 << n` equals 2^n |\n| Right shift | `>>` | Divide by powers of 2 |\n\n\nA common bit manipulation pattern is checking and setting individual bits, which shows up in problems using bitmasks to represent subsets:\n\n\n```python\n# Check if bit i is set\nis_set = (mask & (1 << i)) != 0\n\n# Set bit i\nmask = mask | (1 << i)\n\n# Clear bit i\nmask = mask & ~(1 << i)\n\n# Toggle bit i\nmask = mask ^ (1 << i)\n\n# Count number of set bits\ncount = bin(mask).count('1')\n```\n\n\nPython also provides helpful built-in functions for bit operations:\n\n\n```python\nbin(10) # '0b1010' -- binary string representation\n10 .bit_length() # 4 -- number of bits needed\n```\n\n\nPython does not have an unsigned right shift operator. Since Python integers have arbitrary precision, there is no fixed bit width, so unsigned shift does not apply. For problems that specifically require unsigned right shift behavior (like reversing bits of a 32-bit integer), you need to mask with `& 0xFFFFFFFF` to simulate 32-bit unsigned behavior.\n\n### Control Flow\n\nPython offers several loop forms. Use each where it fits:\n\n\n```python\n# Index-based: when you need the index\nfor i in range(len(nums)):\n ...\n\n# Backward traversal (used in some DP and stack problems)\nfor i in range(n - 1, -1, -1):\n ...\n\n# Value-based: when you only need values\nfor num in nums:\n ...\n\n# Index AND value: the best of both worlds\nfor i, num in enumerate(nums):\n ...\n\n# While: when the termination condition is not index-based\nwhile left < right:\n ...\n```\n\n\n**Use **`enumerate()`** for index-value pairs.** When you need both the index and the value, use `enumerate()` instead of `for i in range(len(nums))`. It is cleaner and less error-prone:\n\n\n```python\n# Instead of this:\nfor i in range(len(nums)):\n print(i, nums[i])\n\n# Write this:\nfor i, num in enumerate(nums):\n print(i, num)\n\n# You can even start from a different index:\nfor i, num in enumerate(nums, start=1):\n print(i, num) # i starts at 1\n```\n\n\n### Short-Circuit Evaluation\n\nPython uses the keywords `and` and `or` for boolean logic:\n\n\n```python\n# Safe: the second condition is only checked if the first is true\nif index < len(nums) and nums[index] == target:\n ...\n\n# Without short-circuit, this would raise IndexError\n# when index >= len(nums)\n```\n\n\nPython's `or` has a useful idiom for default values:\n\n\n```python\nvalue = x or default # If x is falsy (0, None, \"\", []), use default\n```\n\n\nBe careful with this pattern when `0` or `\"\"` are valid values. In those cases, use `x if x is not None else default`.\n\n### The Walrus Operator `:=`\n\nIntroduced in Python 3.8, the walrus operator assigns and returns a value in a single expression. It can make some DSA patterns more concise:\n\n\n```python\n# Without walrus: need to compute twice or use a temp variable\nwhile True:\n line = input()\n if line == \"\":\n break\n process(line)\n\n# With walrus: assign and test in one expression\nwhile (line := input()) != \"\":\n process(line)\n\n# Useful in list comprehensions with expensive computations\nresults = [y for x in data if (y := expensive(x)) > threshold]\n```\n\n\nYou do not need to use the walrus operator in interviews, but knowing it exists helps you read others' solutions.\n\n---\n\n# Functions and Pass-by-Object-Reference\n\nIn DSA problems, extracting logic into helper functions keeps the code clean. On LeetCode, your solution lives inside a class:\n\n\n```python\nclass Solution:\n def twoSum(self, nums: List[int], target: int) -> List[int]:\n ...\n\n def helper(self, arr: List[int], index: int) -> int:\n ...\n```\n\n\nYou can also define nested functions, which is common for DFS/backtracking:\n\n\n```python\nclass Solution:\n def permute(self, nums: List[int]) -> List[List[int]]:\n results = []\n\n def backtrack(path):\n if len(path) == len(nums):\n results.append(path[:]) # Copy!\n return\n for num in nums:\n if num not in path:\n path.append(num)\n backtrack(path)\n path.pop()\n\n backtrack([])\n return results\n```\n\n\nNested functions can access variables from the enclosing scope (like `results` and `nums` above). This is called a **closure** and it is convenient for DSA. It avoids passing extra parameters through recursive calls.\n\n### Pass-by-Object-Reference\n\nPython passes everything by object reference. This means:\n\n- **Mutable objects** (lists, dicts, sets) can be modified in-place by the called function. The caller sees the changes.\n- **Immutable objects** (int, str, tuple, bool) cannot be modified. Any \"modification\" creates a new object, and the caller's variable is unaffected.\n\n\n```python\ndef modify_list(arr):\n arr.append(99) # Modifies the original list\n arr[0] = -1 # Modifies the original list\n\ndef modify_int(x):\n x += 1 # Creates a new int object, does NOT modify caller's x\n\nnums = [1, 2, 3]\nmodify_list(nums)\nprint(nums) # [-1, 2, 3, 99] (modified!)\n\ncount = 5\nmodify_int(count)\nprint(count) # 5 (unchanged!)\n```\n\n\n\n```mermaid\nflowchart TD\n subgraph Mutable[\"Mutable (list, dict, set)\"]\n direction TB\n A[\"caller: nums = [1, 2, 3]\"] --> B[\"function: arr points to SAME list\"]\n B --> C[\"arr.append(99)\"]\n C --> D[\"caller sees [1, 2, 3, 99]\"]\n end\n\n subgraph Immutable[\"Immutable (int, str, tuple)\"]\n direction TB\n E[\"caller: count = 5\"] --> F[\"function: x points to SAME int\"]\n F --> G[\"x += 1 creates NEW int 6\"]\n G --> H[\"caller still sees 5\"]\n end\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#00ceff,stroke:#000,color:#000\n style C fill:#ffa94d,stroke:#000,color:#000\n style D fill:#69db7c,stroke:#000,color:#000\n style E fill:#00ceff,stroke:#000,color:#000\n style F fill:#00ceff,stroke:#000,color:#000\n style G fill:#ffa94d,stroke:#000,color:#000\n style H fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThis distinction matters in recursive and backtracking problems. When you pass a list to a recursive call and add elements to it, those additions are visible to the caller. That is why the backtracking pattern works, adding and removing from a shared list as you explore different branches:\n\n\n```python\ndef backtrack(path, results):\n if is_complete(path):\n results.append(path[:]) # MUST copy with [:] or list(path)\n return\n for choice in choices:\n path.append(choice) # Modify shared list\n backtrack(path, results) # Recurse with modified list\n path.pop() # Undo modification\n```\n\n\nThe `path[:]` when saving results creates a copy. If you wrote `results.append(path)` instead, every entry in `results` would be a reference to the same list, and they would all end up empty after backtracking unwinds. This is a common bug in backtracking solutions.\n\n### The Mutable Default Argument Pitfall\n\nThis is a Python-specific trap to watch for:\n\n\n```python\n# BUG: the default list is created ONCE and shared across ALL calls\ndef add_to(element, target=[]):\n target.append(element)\n return target\n\nadd_to(1) # [1]\nadd_to(2) # [1, 2], NOT [2]! The same list is reused!\nadd_to(3) # [1, 2, 3]\n\n# CORRECT: use None as default, create list inside function\ndef add_to(element, target=None):\n if target is None:\n target = []\n target.append(element)\n return target\n```\n\n\n### Modifying Integers in Nested Functions\n\nIf you need a nested function to modify an integer from the enclosing scope, you need the `nonlocal` keyword:\n\n\n```python\ndef count_nodes(root):\n count = 0\n\n def dfs(node):\n nonlocal count # Required to modify the enclosing scope's count\n if not node:\n return\n count += 1\n dfs(node.left)\n dfs(node.right)\n\n dfs(root)\n return count\n```\n\n\nWithout `nonlocal`, `count += 1` would create a local variable instead of modifying the outer one. Alternatively, you can use a mutable container like a list `[0]` to avoid `nonlocal`, but that is less readable.\n\n---\n\n# Lists as Arrays\n\nLists are the foundational data structure in Python and the starting point for almost every DSA problem.\n\n\n```python\n# Creation\nnums = [1, 2, 3, 4, 5] # Literal initialization\nzeros = [0] * n # n zeros\nvisited = [False] * n # n False values\nfilled = [float('inf')] * n # n infinity values\n```\n\n\n### The 2D Array Trap\n\nWatch for this pattern:\n\n\n```python\n# WRONG: all rows share the SAME inner list!\nmatrix = [[0] * cols] * rows\nmatrix[0][0] = 1\n# matrix[1][0] is ALSO 1 because all rows are the same object!\n\n# CORRECT: use a list comprehension to create independent rows\nmatrix = [[0] * cols for _ in range(rows)]\nmatrix[0][0] = 1\n# matrix[1][0] is still 0, each row is independent\n```\n\n\nThe `[[0] * cols] * rows` pattern is a Python-specific gotcha. Each row is a reference to the same list, so modifying one row modifies all of them. Always use a list comprehension for 2D arrays. This bug indicates a misunderstanding of Python's reference semantics.\n\n### Key List Operations\n\n\n| Operation | Syntax | Time | DSA Use |\n|-----------|--------|------|---------|\n| Append | `lst.append(x)` | O(1) amortized | Building result lists |\n| Pop last | `lst.pop()` | O(1) | Stack operations |\n| Pop at index | `lst.pop(i)` | O(n) | Avoid in tight loops |\n| Insert at index | `lst.insert(i, x)` | O(n) | Avoid in tight loops |\n| Access | `lst[i]` | O(1) | Random access |\n| Update | `lst[i] = x` | O(1) | In-place modification |\n| Length | `len(lst)` | O(1) | Loop bounds |\n| Contains | `x in lst` | O(n) | Use set for O(1) |\n| Reverse in-place | `lst.reverse()` | O(n) | Reverse array |\n| Reversed copy | `lst[::-1]` | O(n) | New reversed list |\n| Sort in-place | `lst.sort()` | O(n log n) | Sorting |\n| Sorted copy | `sorted(lst)` | O(n log n) | New sorted list |\n| Extend | `lst.extend(other)` | O(k) | Concatenate lists |\n| Count | `lst.count(x)` | O(n) | Count occurrences |\n| Index | `lst.index(x)` | O(n) | Find first occurrence |\n| Clear | `lst.clear()` | O(1) | Reset list |\n\n\n### Negative Indexing\n\nPython's negative indexing is one of its most useful features for DSA:\n\n\n```python\nlst = [10, 20, 30, 40, 50]\nlst[-1] # 50 (last element, cleaner than lst[len(lst) - 1])\nlst[-2] # 40 (second to last)\n```\n\n\nThis comes up constantly. Peeking at the top of a stack? `stack[-1]`. Getting the last character of a string? `s[-1]`. Accessing the last row of a matrix? `matrix[-1]`.\n\n### Slicing\n\nSlicing creates a new list from a portion of an existing one. The syntax is `lst[start:stop:step]`, where `start` is inclusive and `stop` is exclusive:\n\n\n```python\nlst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n\nlst[2:5] # [2, 3, 4] -- index 2 to 4\nlst[:3] # [0, 1, 2] -- first 3 elements\nlst[7:] # [7, 8, 9] -- from index 7 to end\nlst[::2] # [0, 2, 4, 6, 8] -- every other element\nlst[::-1] # [9, 8, 7, ..., 0] -- reversed copy\nlst[:] # [0, 1, ..., 9] -- shallow copy of entire list\n```\n\n\nSlicing is particularly useful for:\n\n- **Copying lists:** `copy = lst[:]` or `copy = list(lst)`\n- **Reversing:** `reversed_list = lst[::-1]`\n- **Taking subarrays:** `subarray = lst[i:j]`\n\nBe aware that slicing creates a **new list**, so it costs O(k) time and space where k is the slice size. Do not slice inside a tight loop if you can avoid it.\n\n### List Comprehensions\n\nList comprehensions are one of Python's most useful features for writing concise DSA code:\n\n\n```python\n# Basic comprehension\nsquares = [x**2 for x in range(10)]\n\n# With filter\nevens = [x for x in nums if x % 2 == 0]\n\n# Flattening a 2D list\nflattened = [x for row in matrix for x in row]\n\n# Creating a frequency array\nfreq = [0] * 26 # For lowercase letters\n\n# Generating all pairs\npairs = [(i, j) for i in range(n) for j in range(i + 1, n)]\n```\n\n\n### 2D Arrays and the Directions Pattern\n\n2D arrays appear in every matrix problem (BFS on grid, DP tables, etc.):\n\n\n```python\n# Creation\nmatrix = [[0] * cols for _ in range(rows)]\n\n# Access\nvalue = matrix[row][col]\n\n# Dimensions\nnum_rows = len(matrix)\nnum_cols = len(matrix[0])\n```\n\n\nFor DP problems, you often need a table with one extra row and column for the base case:\n\n\n```python\ndp = [0] * (n + 1)\ndp = [[0] * (n + 1) for _ in range(m + 1)]\n```\n\n\nThe 4-directional neighbor pattern is common in matrix problems:\n\n\n```python\ndirections = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n\nfor dr, dc in directions:\n nr, nc = row + dr, col + dc\n if 0 <= nr < rows and 0 <= nc < cols:\n # Process neighbor\n```\n\n\nFor 8-directional movement (including diagonals), add the four diagonal pairs: `(-1,-1), (-1,1), (1,-1), (1,1)`.\n\n\n```mermaid\nflowchart TD\n subgraph Matrix[\"matrix[3][3]\"]\n direction TB\n R0[\"[0,0] [0,1] [0,2]\"]\n R1[\"[1,0] [1,1] [1,2]\"]\n R2[\"[2,0] [2,1] [2,2]\"]\n end\n\n UP[\"Up
(-1, 0)\"]\n DOWN[\"Down
(+1, 0)\"]\n LEFT[\"Left
(0, -1)\"]\n RIGHT[\"Right
(0, +1)\"]\n\n UP --> R1\n DOWN --> R1\n LEFT --> R1\n RIGHT --> R1\n\n style R0 fill:#00ceff,stroke:#000,color:#000\n style R1 fill:#ffa94d,stroke:#000,color:#000\n style R2 fill:#00ceff,stroke:#000,color:#000\n style UP fill:#69db7c,stroke:#000,color:#000\n style DOWN fill:#69db7c,stroke:#000,color:#000\n style LEFT fill:#69db7c,stroke:#000,color:#000\n style RIGHT fill:#69db7c,stroke:#000,color:#000\n```\n\n\nTuple unpacking with `for dr, dc in directions` and the chained comparison `0 <= nr < rows` make grid traversal code compact and readable.\n\n---\n\n# Strings\n\nStrings in Python are **immutable**. Every time you \"modify\" a string, Python creates a new object. This has a performance implication for DSA:\n\n\n```python\n# BAD: O(n^2) because each += creates a new string\nresult = \"\"\nfor c in chars:\n result += c # Creates a new string every iteration\n\n# GOOD: O(n), build a list then join\nparts = []\nfor c in chars:\n parts.append(c)\nresult = \"\".join(parts)\n\n# BEST: O(n), direct join if you already have an iterable\nresult = \"\".join(chars)\n```\n\n\n### Essential String Methods\n\n\n| Method | Example | DSA Use |\n|--------|---------|---------|\n| `s[i]` | `s[0]` | Access character (no `charAt` needed) |\n| `len(s)` | `len(s)` | Length (built-in function, not method) |\n| `s[a:b]` | `s[0:3]` | Substring via slicing |\n| `s.split()` | `s.split(\" \")` | Tokenize into list |\n| `\"sep\".join(lst)` | `\",\".join(lst)` | Build string from list |\n| `s.strip()` | `s.strip()` | Remove leading/trailing whitespace |\n| `s.isalnum()` | `s.isalnum()` | Alphanumeric check (valid palindrome) |\n| `s.isalpha()` | `s.isalpha()` | Letters only |\n| `s.isdigit()` | `s.isdigit()` | Digits only |\n| `s.lower()` | `s.lower()` | Lowercase conversion |\n| `s.upper()` | `s.upper()` | Uppercase conversion |\n| `s.startswith(p)` | `s.startswith(\"ab\")` | Prefix check |\n| `s.endswith(p)` | `s.endswith(\"ab\")` | Suffix check |\n| `s.find(sub)` | `s.find(\"ab\")` | Find substring (-1 if not found) |\n| `s.count(sub)` | `s.count(\"a\")` | Count occurrences |\n| `s.replace(old, new)` | `s.replace(\"a\", \"b\")` | Replace all occurrences (returns new string) |\n| `sub in s` | `\"ab\" in \"abc\"` | Substring check |\n\n\n### Character Arithmetic with `ord()` and `chr()`\n\nPython does not have a separate `char` type. Characters are just strings of length 1. To do arithmetic on characters (which is common in DSA), use `ord()` and `chr()`:\n\n\n```python\nord('a') # 97\nchr(97) # 'a'\nord(c) - ord('a') # Map 'a'-'z' to 0-25 (frequency arrays)\nord(c) - ord('0') # Map '0'-'9' to 0-9 (digit extraction)\nchr(ord('a') + index) # Map 0-25 back to 'a'-'z'\n```\n\n\nThe `ord(c) - ord('a')` pattern works because characters have numeric values. Subtracting `ord('a')` from a lowercase letter gives its zero-based position. This is how you build frequency arrays without a dictionary:\n\n\n```python\n# Frequency array for lowercase letters (26 slots)\nfreq = [0] * 26\nfor c in s:\n freq[ord(c) - ord('a')] += 1\n# freq[0] = count of 'a', freq[1] = count of 'b', etc.\n```\n\n\nThis is faster and more memory-efficient than `Counter(s)` when you know the character set is limited to lowercase (or uppercase, or digits). However, for most interview problems, `Counter` is perfectly acceptable and more readable.\n\n### String Comparison\n\nPython's `==` operator compares string content, not references:\n\n\n```python\na = \"hello\"\nb = \"hello\"\na == b # True, compares content (no .equals() needed!)\na is b # True for string literals (implementation detail, never rely on this)\n```\n\n\nUse `==` for string equality. The `is` operator checks object identity, which is rarely what you want for strings.\n\n### Useful String Patterns\n\n\n```python\n# Check if string is a palindrome\ns == s[::-1]\n\n# Convert between string and list of characters\nchars = list(s) # String to list of chars\ns = \"\".join(chars) # List of chars back to string\n\n# Convert between string and number\nn = int(\"42\") # String to int\ns = str(42) # Int to string\n\n# F-strings for debugging\nprint(f\"i={i}, val={val}, left={left}, right={right}\")\n```\n\n\n---\n\n# Dictionaries, Sets, and the Collections Module\n\nPython's built-in dictionaries and sets, combined with the `collections` module, provide the data structures used in nearly every DSA problem. Choosing the right collection is often the difference between an O(n) and an O(n^2) solution.\n\n\n```mermaid\nflowchart TD\n BI[\"Python Built-in
Data Structures\"]\n\n SEQ[\"Sequences\"]\n MAP[\"Mappings\"]\n SETS[\"Sets\"]\n\n LIST[\"list
mutable, ordered\"]\n TUPLE[\"tuple
immutable, ordered\"]\n STR[\"str
immutable, ordered\"]\n\n DICT[\"dict
O(1) lookup\"]\n DD[\"defaultdict
auto-default\"]\n CTR[\"Counter
frequency map\"]\n OD[\"OrderedDict
move_to_end\"]\n\n SET[\"set
O(1) lookup\"]\n FS[\"frozenset
immutable set\"]\n\n DQ[\"deque
O(1) both ends\"]\n HP[\"heapq
min-heap on list\"]\n\n BI --> SEQ\n BI --> MAP\n BI --> SETS\n\n SEQ --> LIST\n SEQ --> TUPLE\n SEQ --> STR\n\n MAP --> DICT\n MAP --> DD\n MAP --> CTR\n MAP --> OD\n\n SETS --> SET\n SETS --> FS\n\n LIST --> DQ\n LIST --> HP\n\n style BI fill:#00ceff,stroke:#000,color:#000\n style SEQ fill:#00ceff,stroke:#000,color:#000\n style MAP fill:#00ceff,stroke:#000,color:#000\n style SETS fill:#00ceff,stroke:#000,color:#000\n style LIST fill:#38d9a9,stroke:#000,color:#000\n style TUPLE fill:#38d9a9,stroke:#000,color:#000\n style STR fill:#38d9a9,stroke:#000,color:#000\n style DICT fill:#ffa94d,stroke:#000,color:#000\n style DD fill:#ffa94d,stroke:#000,color:#000\n style CTR fill:#ffa94d,stroke:#000,color:#000\n style OD fill:#ffa94d,stroke:#000,color:#000\n style SET fill:#69db7c,stroke:#000,color:#000\n style FS fill:#69db7c,stroke:#000,color:#000\n style DQ fill:#38d9a9,stroke:#000,color:#000\n style HP fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n### dict: Hash Map\n\n`dict` is Python's built-in hash map. It provides O(1) average-case lookups, inserts, and deletes. Since Python 3.7, dictionaries maintain insertion order.\n\n\n```python\n# Frequency counting: the most common dict pattern\nfreq = {}\nfor c in s:\n freq[c] = freq.get(c, 0) + 1\n\n# Or using a conditional expression\nfreq = {}\nfor c in s:\n if c in freq:\n freq[c] += 1\n else:\n freq[c] = 1\n```\n\n\nKey operations:\n\n\n```python\nd = {}\n\nd[key] = value # Insert or update\nvalue = d[key] # Access (raises KeyError if missing!)\nvalue = d.get(key, 0) # Safe access with default (like getOrDefault)\nkey in d # Check key existence: O(1)\ndel d[key] # Delete key (raises KeyError if missing)\nd.pop(key, default) # Delete and return value (safe with default)\n\n# Iteration\nfor key in d: # Keys only\n ...\nfor value in d.values(): # Values only\n ...\nfor key, value in d.items(): # Key-value pairs\n ...\n\nlen(d) # Number of entries\nd.clear() # Remove all entries\n```\n\n\n**A safety point:** `d[key]` raises `KeyError` if the key does not exist. Always use `d.get(key, default)` for safe access, or check `key in d` first. Forgetting this guard is a common source of bugs in interview code.\n\n### defaultdict: Auto-Default Values\n\n`defaultdict` from the `collections` module automatically creates a default value when you access a missing key. This eliminates the \"check if key exists, create if not\" pattern:\n\n\n```python\nfrom collections import defaultdict\n\n# Build adjacency list: one line per edge, no existence check needed\ngraph = defaultdict(list)\nfor u, v in edges:\n graph[u].append(v)\n graph[v].append(u) # Omit for directed graphs\n\n# Frequency counting\nfreq = defaultdict(int)\nfor c in s:\n freq[c] += 1 # Missing keys default to 0\n\n# Grouping by key\ngroups = defaultdict(list)\nfor word in words:\n key = tuple(sorted(word)) # Anagram key\n groups[key].append(word)\n```\n\n\nCompare this to the verbose alternative:\n\n\n```python\n# Without defaultdict (verbose)\ngraph = {}\nfor u, v in edges:\n if u not in graph:\n graph[u] = []\n graph[u].append(v)\n\n# With defaultdict (clean)\ngraph = defaultdict(list)\nfor u, v in edges:\n graph[u].append(v)\n```\n\n\nCommon default factories:\n\n\n| Factory | Default Value | Use Case |\n|---------|--------------|----------|\n| `int` | `0` | Frequency counting |\n| `list` | `[]` | Adjacency lists, grouping |\n| `set` | `set()` | Unique neighbors, deduplication |\n| `lambda: float('inf')` | `inf` | Distance maps in shortest path |\n\n\n### Counter: Purpose-Built Frequency Counting\n\n`Counter` from `collections` is the most concise way to count frequencies:\n\n\n```python\nfrom collections import Counter\n\nfreq = Counter(\"abracadabra\")\n# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})\n\nfreq.most_common(2) # [('a', 5), ('b', 2)] -- top 2 most common\nfreq.most_common() # All elements sorted by frequency (descending)\nfreq['z'] # 0 (missing keys return 0, NOT KeyError)\nfreq.total() # 11 (sum of all counts, Python 3.10+)\n\n# Counter from a list\nnums_freq = Counter([1, 2, 2, 3, 3, 3])\n# Counter({3: 3, 2: 2, 1: 1})\n```\n\n\nCounter arithmetic is useful for DSA:\n\n\n```python\nc1 = Counter(\"aab\") # Counter({'a': 2, 'b': 1})\nc2 = Counter(\"abb\") # Counter({'b': 2, 'a': 1})\n\nc1 - c2 # Counter({'a': 1}) -- subtract counts (drops non-positive)\nc1 & c2 # Counter({'a': 1, 'b': 1}) -- intersection (min of each count)\nc1 | c2 # Counter({'a': 2, 'b': 2}) -- union (max of each count)\nc1 + c2 # Counter({'a': 3, 'b': 3}) -- add counts\n\n# Direct comparison for anagram check\nCounter(\"listen\") == Counter(\"silent\") # True\n```\n\n\n### set: Hash Set\n\n`set` provides O(1) average-case membership testing:\n\n\n```python\nvisited = set()\nvisited.add(node) # Add element\nnode in visited # O(1) membership test\nvisited.remove(node) # Remove (raises KeyError if missing)\nvisited.discard(node) # Remove (NO error if missing, prefer this)\nlen(visited) # Number of elements\n```\n\n\nUnlike some languages, `set.add()` returns nothing, so you detect duplicates by checking membership before adding:\n\n\n```python\nseen = set()\nfor num in nums:\n if num in seen:\n # num is a duplicate\n pass\n seen.add(num)\n```\n\n\nSet operations are useful for certain DSA problems:\n\n\n```python\na = {1, 2, 3, 4}\nb = {3, 4, 5, 6}\n\na | b # {1, 2, 3, 4, 5, 6} -- union\na & b # {3, 4} -- intersection\na - b # {1, 2} -- difference (in a but not b)\na ^ b # {1, 2, 5, 6} -- symmetric difference\na <= b # False -- subset check\n```\n\n\n### OrderedDict\n\nSince Python 3.7, regular `dict` maintains insertion order. `OrderedDict` from `collections` is still useful for one specific operation: `move_to_end()`, which is used in LRU cache implementations:\n\n\n```python\nfrom collections import OrderedDict\n\nclass LRUCache:\n def __init__(self, capacity: int):\n self.cache = OrderedDict()\n self.capacity = capacity\n\n def get(self, key: int) -> int:\n if key not in self.cache:\n return -1\n self.cache.move_to_end(key) # Mark as recently used\n return self.cache[key]\n\n def put(self, key: int, value: int) -> None:\n if key in self.cache:\n self.cache.move_to_end(key)\n self.cache[key] = value\n if len(self.cache) > self.capacity:\n self.cache.popitem(last=False) # Remove oldest (first item)\n```\n\n\n### Hashability: What Can Be a Dict Key or Set Element?\n\nHashability matters for Python DSA. Only **hashable** objects can be dict keys or set elements. The rule is simple: **mutable objects are not hashable, immutable objects are**.\n\n\n| Type | Hashable? | Can Be Dict Key / Set Element? |\n|------|-----------|-------------------------------|\n| `int`, `float`, `bool` | Yes | Yes |\n| `str` | Yes | Yes |\n| `tuple` (of hashable elements) | Yes | Yes |\n| `frozenset` | Yes | Yes |\n| `list` | No | No |\n| `dict` | No | No |\n| `set` | No | No |\n\n\nThis comes up constantly in DSA:\n\n\n```python\n# You CANNOT add a list to a set\nvisited = set()\nvisited.add([1, 2]) # TypeError: unhashable type: 'list'\n\n# Convert to tuple first\nvisited.add((1, 2)) # Works!\n\n# Common pattern: track visited states in BFS/DFS\nvisited = set()\nstate = (row, col)\nvisited.add(state)\n\n# For memoization: state must be hashable\nmemo = {}\nstate = (index, remaining, flag)\nif state in memo:\n return memo[state]\n```\n\n\n### Collections Quick Reference\n\n\n| Collection | Python Type | Key Methods | Time Complexity | DSA Use Case |\n|-----------|-------------|-------------|-----------------|--------------|\n| Dynamic array | `list` | `append`, `pop`, `[]`, `len` | O(1) append/access | Result lists, stacks |\n| Hash map | `dict` | `[]`, `get`, `in`, `items` | O(1) average | Frequency counting, lookups |\n| Hash set | `set` | `add`, `in`, `discard` | O(1) average | Visited tracking, duplicates |\n| Auto-default map | `defaultdict` | Same as dict + auto-default | O(1) average | Adjacency lists, grouping |\n| Frequency map | `Counter` | `most_common`, arithmetic | O(1) average | Anagram, window problems |\n| Ordered map | `OrderedDict` | `move_to_end`, `popitem` | O(1) average | LRU cache |\n| Double-ended queue | `deque` | `append`, `popleft`, `appendleft` | O(1) both ends | BFS, sliding window |\n| Min-heap | `heapq` on `list` | `heappush`, `heappop` | O(log n) push/pop | Top-K, Dijkstra |\n| Sorted list | `SortedList` | `add`, `remove`, `bisect` | O(log n) | Sliding window sorted access |\n| Immutable sequence | `tuple` | `[]`, `in`, unpacking | O(1) access | Dict keys, heap elements, states |\n| Immutable set | `frozenset` | Same as set (read-only) | O(1) lookup | Set of sets, dict keys |\n\n\n---\n\n# Tuples: Python's Built-in Pairs\n\nPython tuples are immutable, fixed-size sequences. They are the standard way to group a small number of related values, and they simplify many DSA patterns: coordinates, edges, intervals, and heap entries.\n\n\n```python\n# As a pair (coordinates, edges, intervals)\npoint = (3, 4)\nx, y = point # Tuple unpacking\n\n# As a triple or more\nedge = (weight, u, v)\nw, u, v = edge\n\n# Multiple return values\ndef divmod_custom(a, b):\n return a // b, a % b # Returns a tuple\nquotient, remainder = divmod_custom(7, 3)\n```\n\n\n### Why Tuples Matter for DSA\n\n**1. Tuples are hashable** (unlike lists), so they can be dict keys and set elements:\n\n\n```python\nvisited = set()\nvisited.add((row, col)) # Track grid positions\nvisited.add((row, col, dir)) # Track states in BFS\n\nmemo = {}\nmemo[(i, j)] = result # Memoization key\n```\n\n\n**2. Tuples compare lexicographically**, which is useful for heap operations:\n\n\n```python\n(1, 3) < (1, 5) # True (first elements equal, compare second)\n(1, 5) < (2, 1) # True (first element smaller)\n(2, 1) < (2, 1) # False (equal)\n```\n\n\nThis means you can push tuples onto a heap and they will be ordered by the first element, with ties broken by the second element, and so on:\n\n\n```python\nfrom heapq import heappush, heappop\n\n# Dijkstra pattern: sort by distance, break ties by node ID\npq = []\nheappush(pq, (0, start_node)) # (distance, node)\ndist, node = heappop(pq) # Smallest distance first\n\n# Task scheduling: sort by deadline, then by profit\ntasks = []\nheappush(tasks, (deadline, -profit, task_id))\n```\n\n\n**3. Tuple unpacking** makes code cleaner:\n\n\n```python\n# Clean iteration over edges\nfor u, v in edges:\n graph[u].append(v)\n\n# Clean iteration over coordinates\nfor r, c in queue:\n process(r, c)\n\n# Swap\na, b = b, a\n\n# Fibonacci in one line\na, b = b, a + b\n```\n\n\n---\n\n# deque: BFS and Sliding Window Foundation\n\n`deque` (double-ended queue) from `collections` provides O(1) operations at both ends. Use it for BFS, sliding window problems, and monotonic deque patterns.\n\n\n```python\nfrom collections import deque\n```\n\n\n### BFS Template\n\nEvery BFS implementation starts with a deque:\n\n\n```python\nqueue = deque([(start_row, start_col)])\nvisited = set()\nvisited.add((start_row, start_col))\n\nwhile queue:\n row, col = queue.popleft() # O(1) dequeue from left\n # Process current cell\n for dr, dc in directions:\n nr, nc = row + dr, col + dc\n if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:\n visited.add((nr, nc))\n queue.append((nr, nc)) # O(1) enqueue to right\n```\n\n\nFor level-order BFS (where you need to process all nodes at the current level before moving to the next), capture the queue size:\n\n\n```python\nlevel = 0\nwhile queue:\n size = len(queue)\n for _ in range(size):\n node = queue.popleft()\n # Process node at current level\n for neighbor in graph[node]:\n if neighbor not in visited:\n visited.add(neighbor)\n queue.append(neighbor)\n level += 1\n```\n\n\n### deque Operations\n\n\n```python\ndq = deque()\n\n# Right end (like a regular queue/stack)\ndq.append(val) # Add to right: O(1)\ndq.pop() # Remove from right: O(1)\n\n# Left end (the deque advantage)\ndq.appendleft(val) # Add to left: O(1)\ndq.popleft() # Remove from left: O(1)\n\n# Peek (no dedicated method, just index)\ndq[0] # Peek left\ndq[-1] # Peek right\n\n# Other\nlen(dq) # Size\nbool(dq) # True if non-empty (useful in while loops)\n```\n\n\n\n```mermaid\nflowchart LR\n AL[\"appendleft()\"] --> DQ[\"deque
[front ... back]\"]\n DQ --> PL[\"popleft()\"]\n AR[\"append()\"] --> DQ\n DQ --> PR[\"pop()\"]\n\n style AL fill:#69db7c,stroke:#000,color:#000\n style AR fill:#69db7c,stroke:#000,color:#000\n style PL fill:#ff8787,stroke:#000,color:#000\n style PR fill:#ff8787,stroke:#000,color:#000\n style DQ fill:#00ceff,stroke:#000,color:#000\n```\n\n\n### Monotonic Deque Pattern\n\nThe monotonic deque is used in \"sliding window maximum/minimum\" problems:\n\n\n```python\n# Sliding window maximum\ndef maxSlidingWindow(nums, k):\n dq = deque() # Stores indices, maintains decreasing order of values\n result = []\n\n for i in range(len(nums)):\n # Remove indices outside the window\n while dq and dq[0] < i - k + 1:\n dq.popleft()\n\n # Remove smaller elements (they can never be the max)\n while dq and nums[dq[-1]] < nums[i]:\n dq.pop()\n\n dq.append(i)\n\n if i >= k - 1:\n result.append(nums[dq[0]]) # Front of deque is the max\n\n return result\n```\n\n\n### Bounded deque\n\nYou can create a deque with a maximum size. When full, adding to one end automatically removes from the other:\n\n\n```python\nwindow = deque(maxlen=3)\nwindow.append(1) # deque([1])\nwindow.append(2) # deque([1, 2])\nwindow.append(3) # deque([1, 2, 3])\nwindow.append(4) # deque([2, 3, 4]) (1 was automatically removed)\n```\n\n\n---\n\n# heapq: Min-Heap and the Max-Heap Trick\n\nPython's `heapq` module provides heap operations on a regular list. The heap is always a **min-heap**, meaning the smallest element is always at index 0.\n\n\n```python\nfrom heapq import heappush, heappop, heapify, nlargest, nsmallest\n```\n\n\n### Basic Operations\n\n\n```python\nheap = []\nheappush(heap, 5) # Insert: O(log n)\nheappush(heap, 2)\nheappush(heap, 8)\n\nsmallest = heappop(heap) # Remove and return smallest: O(log n)\n# smallest = 2\n\npeek = heap[0] # View smallest without removing: O(1)\n\n# Heapify an existing list: O(n), faster than n individual pushes\nnums = [5, 2, 8, 1, 9]\nheapify(nums) # Converts in-place to a min-heap\n```\n\n\n### The Max-Heap Trick\n\nPython only provides a min-heap. To get a max-heap, **negate the values**:\n\n\n```python\nmax_heap = []\nheappush(max_heap, -5) # Store negative\nheappush(max_heap, -2)\nheappush(max_heap, -8)\n\nlargest = -heappop(max_heap) # Negate when extracting\n# largest = 8\n\npeek_max = -max_heap[0] # Negate when peeking\n```\n\n\nThis works because negating reverses the ordering: if `a < b`, then `-a > -b`.\n\n### Tuples in Heaps\n\nSince tuples compare lexicographically, you can push tuples to sort by multiple fields. The first element of the tuple determines the primary sort order:\n\n\n```python\n# Dijkstra's algorithm: sort by distance\npq = []\nheappush(pq, (0, start_node)) # (distance, node)\ndist, node = heappop(pq)\n\n# Task scheduling: sort by end time, break ties by start time\npq = []\nheappush(pq, (end_time, start_time, task_id))\n\n# Merge K sorted lists: sort by value, track which list it came from\npq = []\nfor i, lst in enumerate(lists):\n if lst:\n heappush(pq, (lst[0].val, i, lst[0]))\n```\n\n\n**Caution with tuples:** If the first elements are equal, Python compares the second elements. If the second elements are not comparable (e.g., custom objects without `__lt__`), you get a `TypeError`. Always include a tie-breaking field (like an index or counter) as the second element:\n\n\n```python\n# BAD: if distances are equal, comparing ListNode objects will fail\nheappush(pq, (distance, node_object))\n\n# GOOD: include a counter as tie-breaker\ncounter = 0\nheappush(pq, (distance, counter, node_object))\ncounter += 1\n```\n\n\n### heapq Utility Functions\n\n\n```python\n# Find K largest/smallest without sorting the entire list\nnlargest(3, nums) # [9, 8, 5]\nnsmallest(3, nums) # [1, 2, 5]\n\n# With key function\nnlargest(3, students, key=lambda s: s.gpa)\n\n# heappushpop: push then pop (more efficient than separate operations)\nfrom heapq import heappushpop\nresult = heappushpop(heap, val) # Push val, then pop smallest\n\n# heapreplace: pop then push\nfrom heapq import heapreplace\nresult = heapreplace(heap, val) # Pop smallest, then push val\n```\n\n\nOne important limitation: `heapq` does **not** support efficient removal of arbitrary elements. Removing a specific element that is not at the root requires an O(n) scan, and there is no `remove` method. If you need to invalidate heap elements, use **lazy deletion**: mark elements as deleted and skip them when they surface via `heappop()`. Alternatively, use `SortedList` from `sortedcontainers` which supports O(log n) removal.\n\n---\n\n# Sorted Containers and bisect\n\nPython does not ship a balanced binary search tree in its standard library, but it offers two ways to work with sorted data: the `bisect` module for binary search on sorted lists, and the third-party `sortedcontainers` library (available on LeetCode) for O(log n) sorted maps and sets.\n\n### bisect: Binary Search on Sorted Lists\n\nThe `bisect` module performs binary search to find insertion points in a sorted list:\n\n\n```python\nfrom bisect import bisect_left, bisect_right, insort\n\nsorted_list = [1, 3, 5, 7, 9]\n\nbisect_left(sorted_list, 5) # 2 (leftmost position where 5 can be inserted)\nbisect_right(sorted_list, 5) # 3 (rightmost position where 5 can be inserted)\nbisect_left(sorted_list, 4) # 2 (insertion point for 4)\nbisect_left(sorted_list, 0) # 0 (insertion point for 0)\nbisect_left(sorted_list, 10) # 5 (insertion point for 10)\n```\n\n\nThe difference between `bisect_left` and `bisect_right` matters when the value exists in the list:\n\n- `bisect_left(lst, x)`: returns the index of the **leftmost** position where `x` can be inserted (i.e., the index of the first element `>= x`)\n- `bisect_right(lst, x)`: returns the index of the **rightmost** position where `x` can be inserted (i.e., the index of the first element `> x`)\n\nThis makes `bisect_left` useful for \"find the first element >= target\" and `bisect_right` for \"find the first element > target\":\n\n\n```python\n# Find floor (largest element <= target)\ni = bisect_right(sorted_list, target) - 1\nfloor_val = sorted_list[i] if i >= 0 else None\n\n# Find ceiling (smallest element >= target)\ni = bisect_left(sorted_list, target)\nceiling_val = sorted_list[i] if i < len(sorted_list) else None\n\n# Count elements in range [lo, hi]\ncount = bisect_right(sorted_list, hi) - bisect_left(sorted_list, lo)\n```\n\n\n**Insert while maintaining sort order:**\n\n\n```python\ninsort(sorted_list, 4) # [1, 3, 4, 5, 7, 9]\n```\n\n\nNote that `insort` is O(log n) for the search but O(n) for the insertion (because shifting elements in a list is O(n)). For large lists with frequent insertions, use `SortedList` instead.\n\n### SortedList, SortedDict, SortedSet\n\nThe `sortedcontainers` library provides three O(log n) sorted data structures: `SortedList`, `SortedDict`, and `SortedSet`.\n\n\n```python\nfrom sortedcontainers import SortedList, SortedDict, SortedSet\n\n# SortedList: maintains elements in sorted order, allows duplicates\nsl = SortedList([5, 1, 3, 1]) # SortedList([1, 1, 3, 5])\nsl.add(2) # O(log n) insert\nsl.remove(3) # O(log n) remove (raises ValueError if missing)\nsl.discard(99) # O(log n) remove (no error if missing)\nsl[0] # 1 (smallest element)\nsl[-1] # 5 (largest element)\nsl.bisect_left(3) # Index where 3 starts\nsl.bisect_right(3) # Index after where 3 ends\nsl.irange(2, 5) # Iterator over elements in [2, 5]\n\n# SortedDict: dictionary that keeps keys in sorted order\nsd = SortedDict()\nsd[5] = \"five\"\nsd[1] = \"one\"\nsd[3] = \"three\"\nsd.peekitem(0) # (1, \"one\") -- smallest key\nsd.peekitem(-1) # (5, \"five\") -- largest key\nsd.keys() # SortedKeysView([1, 3, 5])\nsd.irange(2, 5) # Iterator over keys in [2, 5]\n\n# SortedSet: set that keeps elements in sorted order, no duplicates\nss = SortedSet([5, 1, 3])\nss.add(2)\nss[0] # 1 (smallest)\nss[-1] # 5 (largest)\n```\n\n\nCommon neighbor queries on a `SortedList`:\n\n\n| Query | Expression | Notes |\n|-------|------------|-------|\n| Floor (largest <= x) | `sl[sl.bisect_right(x) - 1]` | Check index >= 0 first |\n| Ceiling (smallest >= x) | `sl[sl.bisect_left(x)]` | Check index < len(sl) first |\n| Strictly lower (largest < x) | `sl[sl.bisect_left(x) - 1]` | Check index >= 0 first |\n| Strictly higher (smallest > x) | `sl[sl.bisect_right(x)]` | Check index < len(sl) first |\n| Smallest element | `sl[0]` | O(1) access |\n| Largest element | `sl[-1]` | O(1) access |\n\n\n---\n\n# Sorting and Custom Comparators\n\nSorting is a prerequisite for many algorithms: binary search, two pointers on sorted arrays, merge intervals, and greedy approaches.\n\n\n```python\n# Sort list in-place (modifies the list)\nnums = [3, 1, 4, 1, 5]\nnums.sort() # [1, 1, 3, 4, 5]\n\n# Return a new sorted list (original unchanged)\nsorted_nums = sorted(nums)\n\n# Descending order\nnums.sort(reverse=True) # [5, 4, 3, 1, 1]\nsorted(nums, reverse=True)\n```\n\n\n### Custom Sorting with key=\n\nThe `key` parameter takes a function that extracts a comparison key from each element. This is how you sort by custom criteria:\n\n\n```python\n# Sort intervals by start time (merge intervals pattern)\nintervals = [[1, 3], [2, 6], [8, 10]]\nintervals.sort(key=lambda x: x[0])\n\n# Sort strings by length\nwords.sort(key=lambda w: len(w))\n\n# Multi-key sort: by length first, then alphabetically for ties\nwords.sort(key=lambda w: (len(w), w))\n\n# Sort by absolute value\nnums.sort(key=abs)\n\n# Sort by frequency (most common first)\nfrom collections import Counter\nfreq = Counter(nums)\nnums.sort(key=lambda x: -freq[x])\n```\n\n\nThe tuple trick handles multi-key sorting cleanly. Python compares tuples lexicographically, so `(len(w), w)` sorts by length first, then alphabetically for words of the same length.\n\nTo sort one key ascending and another descending, negate the ascending key (for numbers) or reverse the sort:\n\n\n```python\n# Sort by score descending, then name ascending\nstudents.sort(key=lambda s: (-s.score, s.name))\n```\n\n\n### cmp_to_key: When key= Is Not Enough\n\nFor rare problems where the comparison logic cannot be expressed as a simple key extraction, use `cmp_to_key`:\n\n\n```python\nfrom functools import cmp_to_key\n\n# \"Largest Number\" problem: arrange numbers to form largest value\n# Comparison: \"9\" + \"34\" = \"934\" > \"349\" = \"34\" + \"9\", so \"9\" comes first\ndef compare(a, b):\n if a + b > b + a:\n return -1 # a should come first\n elif a + b < b + a:\n return 1 # b should come first\n return 0\n\nnums_str = [str(n) for n in nums]\nnums_str.sort(key=cmp_to_key(compare))\nresult = \"\".join(nums_str)\n```\n\n\n### Sort Stability\n\nPython's sort is **stable** (it uses TimSort). Elements that compare equal retain their relative order from the original list. This is useful for multi-key sorting. You can sort by secondary key first, then by primary key, and the secondary order is preserved within groups of equal primary keys:\n\n\n```python\n# Sort by grade (primary), then by name (secondary)\n# Method 1: single sort with tuple key (recommended)\nstudents.sort(key=lambda s: (s.grade, s.name))\n\n# Method 2: two stable sorts (works but less efficient)\nstudents.sort(key=lambda s: s.name) # Sort by secondary key first\nstudents.sort(key=lambda s: s.grade) # Then by primary key (stable!)\n```\n\n\n---\n\n# Functional Patterns and Pythonic Idioms for DSA\n\nPython offers several patterns that make DSA code more concise and readable. They reduce the number of lines you write in an interview, leaving more time for the actual algorithm.\n\n### List Comprehensions and Generator Expressions\n\nList comprehensions create lists in a single expression:\n\n\n```python\n# Basic comprehension\nsquares = [x**2 for x in range(10)]\n\n# With filter\nevens = [x for x in nums if x % 2 == 0]\n\n# Nested comprehension (all pairs)\npairs = [(i, j) for i in range(n) for j in range(i + 1, n)]\n\n# Flattening a 2D list\nflattened = [x for row in matrix for x in row]\n```\n\n\nGenerator expressions are like list comprehensions but lazy. They do not create the entire list in memory:\n\n\n```python\n# Generator expression (uses () instead of [])\ntotal = sum(x**2 for x in range(10)) # No intermediate list created\n\n# Useful with any() and all()\nhas_negative = any(x < 0 for x in nums)\nall_positive = all(x > 0 for x in nums)\n\n# Find first match\nfirst_even = next(x for x in nums if x % 2 == 0) # StopIteration if none\nfirst_even = next((x for x in nums if x % 2 == 0), None) # None if none\n```\n\n\n### zip(): Parallel Iteration\n\n`zip()` pairs up elements from multiple iterables:\n\n\n```python\n# Iterate over two lists in parallel\nfor a, b in zip(list1, list2):\n ...\n\n# Useful for comparing adjacent elements\nfor curr, nxt in zip(nums, nums[1:]):\n if curr > nxt:\n print(\"Not sorted!\")\n\n# Transpose a matrix\nmatrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\ntransposed = list(zip(*matrix))\n# [(1, 4, 7), (2, 5, 8), (3, 6, 9)]\n\n# Unzip (separate paired data)\npairs = [(1, 'a'), (2, 'b'), (3, 'c')]\nnums, letters = zip(*pairs)\n# nums = (1, 2, 3), letters = ('a', 'b', 'c')\n```\n\n\n### reversed(): Reverse Without Copying\n\n`reversed()` returns an iterator that traverses in reverse. Unlike `lst[::-1]`, it does not create a new list:\n\n\n```python\n# Iterate backward without creating a new list\nfor val in reversed(nums):\n ...\n\n# Reverse a string\nreversed_s = \"\".join(reversed(s))\n\n# Or more commonly with slicing:\nreversed_s = s[::-1]\n```\n\n\n### Multiple Assignment and Unpacking\n\n\n```python\n# Swap\na, b = b, a\n\n# Unpack first and rest\nfirst, *rest = [1, 2, 3, 4] # first=1, rest=[2, 3, 4]\n\n# Unpack first, middle, last\nfirst, *middle, last = [1, 2, 3, 4] # first=1, middle=[2, 3], last=4\n\n# Ignore values with _\n_, val, _ = (1, 2, 3) # Only care about val\n\n# Unpack in loops\nfor i, (key, value) in enumerate(d.items()):\n ...\n```\n\n\n### Counter Arithmetic in Sliding Window\n\nThis pattern is useful for sliding window problems:\n\n\n```python\nfrom collections import Counter\n\n# Find all anagrams of p in s\ndef findAnagrams(s, p):\n if len(p) > len(s):\n return []\n\n p_count = Counter(p)\n window = Counter(s[:len(p)])\n result = []\n\n if window == p_count: # Direct Counter comparison!\n result.append(0)\n\n for i in range(len(p), len(s)):\n # Add new character to window\n window[s[i]] += 1\n # Remove old character from window\n old_char = s[i - len(p)]\n window[old_char] -= 1\n if window[old_char] == 0:\n del window[old_char] # Remove zero-count entries for clean comparison\n\n if window == p_count:\n result.append(i - len(p) + 1)\n\n return result\n```\n\n\n### map() and filter()\n\nWhile list comprehensions are generally preferred, `map()` can be useful for type conversions:\n\n\n```python\n# Convert list of strings to ints\nnums = list(map(int, input().split()))\n\n# Convert list of ints to strings (for joining)\nresult = \"\".join(map(str, nums))\n```\n\n\n---\n\n# Memoization with lru_cache and cache\n\nThe `@cache` and `@lru_cache` decorators turn any recursive function into a memoized solution with zero boilerplate. Many DP problems that would normally require a manual memo dictionary or a full bottom-up table can be solved with a decorated recursive function.\n\n### Basic Usage\n\n\n```python\nfrom functools import lru_cache, cache\n\n# Fibonacci with memoization: no manual memo dictionary needed\n@cache # Python 3.9+\ndef fib(n):\n if n <= 1:\n return n\n return fib(n - 1) + fib(n - 2)\n\n# Equivalent using lru_cache (works in Python 3.2+)\n@lru_cache(maxsize=None)\ndef fib(n):\n if n <= 1:\n return n\n return fib(n - 1) + fib(n - 2)\n```\n\n\n`@cache` is shorthand for `@lru_cache(maxsize=None)`, introduced in Python 3.9. Both cache all results indefinitely.\n\n### 2D DP Example\n\n\n```python\n# Longest Common Subsequence\n@cache\ndef lcs(i, j):\n if i < 0 or j < 0:\n return 0\n if s[i] == t[j]:\n return 1 + lcs(i - 1, j - 1)\n return max(lcs(i - 1, j), lcs(i, j - 1))\n\nresult = lcs(len(s) - 1, len(t) - 1)\n```\n\n\n### Using @cache on LeetCode\n\nOn LeetCode, your solution is a class method. Here is how to use `@cache` inside a class:\n\n\n```python\nclass Solution:\n def coinChange(self, coins: List[int], amount: int) -> int:\n\n @cache\n def dp(remaining):\n if remaining == 0:\n return 0\n if remaining < 0:\n return float('inf')\n return 1 + min(dp(remaining - c) for c in coins)\n\n result = dp(amount)\n return result if result != float('inf') else -1\n```\n\n\nThe nested function approach works cleanly because `coins` is captured from the enclosing scope and does not need to be a parameter (which would affect the cache key).\n\n### Key Constraints\n\n**Arguments must be hashable.** You cannot pass lists to a cached function. Convert them to tuples:\n\n\n```python\n# WRONG: list is not hashable\n@cache\ndef dp(index, remaining_items): # remaining_items is a list\n ...\n\n# CORRECT: use a tuple or frozenset\n@cache\ndef dp(index, remaining_items): # remaining_items is a tuple\n ...\n\n# Call with tuple\ndp(0, tuple(items))\n```\n\n\n**Remember to clear the cache** if you run multiple test cases and the cached function uses external state. On LeetCode, this is rarely needed because each test case creates a new `Solution` instance. But in local testing:\n\n\n```python\nfib.cache_clear() # Reset the cache\n```\n\n\n### When to Use Manual Memo Instead\n\nSometimes `@cache` is not the best fit:\n\n\n```python\n# Manual memo dictionary\nmemo = {}\ndef dp(state):\n if state in memo:\n return memo[state]\n # ... compute result ...\n memo[state] = result\n return result\n```\n\n\nUse manual memo when:\n\n- You need to pass mutable state that cannot be made hashable\n- You want to inspect or modify the cache during computation\n- You are working with a very large state space and want to control memory\n- The recursion is extremely deep (the decorator adds slight overhead per call)\n\n---\n\n# Recursion, the Call Stack, and sys.setrecursionlimit\n\nEvery function call in Python goes on the **call stack**. Python's default recursion limit is 1000, which is extremely low for DSA problems:\n\n\n```python\nimport sys\nprint(sys.getrecursionlimit()) # 1000\n\n# This will crash for n > ~1000\ndef factorial(n):\n if n <= 1:\n return 1\n return n * factorial(n - 1)\n\nfactorial(5000) # RecursionError: maximum recursion depth exceeded\n```\n\n\nThe fix is one line:\n\n\n```python\nimport sys\nsys.setrecursionlimit(10**6) # Set to 1 million\n```\n\n\n### When to Worry About Stack Depth\n\n\n| Scenario | Typical Depth | Risk |\n|----------|--------------|------|\n| Balanced binary tree (n nodes) | O(log n) | Safe for n up to 10^6 |\n| Linked list / skewed tree (n nodes) | O(n) | Dangerous if n > 1000 (default limit) |\n| Backtracking (k choices, depth d) | O(d) | Usually safe (d is small) |\n| DFS on graph (n nodes) | O(n) | Set recursionlimit for large n |\n\n\n### Converting Recursion to Iteration\n\nWhen recursion depth is proportional to input size and the input can be large, convert to iteration using an explicit stack:\n\n\n```python\n# Recursive DFS (risks RecursionError for large graphs)\ndef dfs(node, visited, graph):\n visited.add(node)\n for neighbor in graph[node]:\n if neighbor not in visited:\n dfs(neighbor, visited, graph)\n\n# Iterative DFS (safe for any depth)\ndef dfs(start, visited, graph):\n stack = [start]\n while stack:\n node = stack.pop()\n if node in visited:\n continue\n visited.add(node)\n for neighbor in graph[node]:\n if neighbor not in visited:\n stack.append(neighbor)\n```\n\n\nNote that Python does **not** optimize tail recursion. Unlike some functional languages, a tail-recursive function in Python still adds a frame to the call stack on every call.\n\n---\n\n# Graph Representation Patterns\n\nGraphs appear in a large portion of DSA problems. Python does not have a built-in graph class, so you need to build representations yourself. There are two common approaches.\n\n### Approach 1: defaultdict(list)\n\nUse when node IDs can be anything (integers, strings, etc.):\n\n\n```python\nfrom collections import defaultdict\n\ngraph = defaultdict(list)\nfor u, v in edges:\n graph[u].append(v)\n graph[v].append(u) # Omit for directed graphs\n\n# Access neighbors (always returns a list, even for missing nodes)\nfor neighbor in graph[node]:\n ...\n```\n\n\n### Approach 2: List of Lists (when nodes are 0 to n-1)\n\nMore memory-efficient when node IDs are contiguous integers:\n\n\n```python\nn = 5 # number of nodes\ngraph = [[] for _ in range(n)]\n\nfor u, v in edges:\n graph[u].append(v)\n graph[v].append(u) # Omit for directed graphs\n\n# Access neighbors\nfor neighbor in graph[node]:\n ...\n```\n\n\n### Weighted Graphs\n\nStore tuples of `(neighbor, weight)`:\n\n\n```python\n# Using defaultdict\ngraph = defaultdict(list)\nfor u, v, w in edges:\n graph[u].append((v, w))\n graph[v].append((u, w)) # Omit for directed\n\n# Dijkstra pattern\nfrom heapq import heappush, heappop\n\ndef dijkstra(graph, start, n):\n dist = [float('inf')] * n\n dist[start] = 0\n pq = [(0, start)] # (distance, node)\n\n while pq:\n d, node = heappop(pq)\n if d > dist[node]:\n continue # Skip outdated entries\n for neighbor, weight in graph[node]:\n new_dist = d + weight\n if new_dist < dist[neighbor]:\n dist[neighbor] = new_dist\n heappush(pq, (new_dist, neighbor))\n\n return dist\n```\n\n\n\n```mermaid\nflowchart LR\n subgraph AdjDict[\"defaultdict(list)\"]\n K0[\"Key: 0\"] --> V0[\"[(1, w), (2, w)]\"]\n K1[\"Key: 1\"] --> V1[\"[(0, w), (3, w)]\"]\n K2[\"Key: 2\"] --> V2[\"[(0, w), (3, w)]\"]\n K3[\"Key: 3\"] --> V3[\"[(1, w), (2, w)]\"]\n end\n\n subgraph AdjList[\"List of Lists\"]\n N0[\"graph[0]\"] --> L0[\"[(1, w), (2, w)]\"]\n N1[\"graph[1]\"] --> L1[\"[(0, w), (3, w)]\"]\n N2[\"graph[2]\"] --> L2[\"[(0, w), (3, w)]\"]\n N3[\"graph[3]\"] --> L3[\"[(1, w), (2, w)]\"]\n end\n\n style K0 fill:#ffa94d,stroke:#000,color:#000\n style K1 fill:#ffa94d,stroke:#000,color:#000\n style K2 fill:#ffa94d,stroke:#000,color:#000\n style K3 fill:#ffa94d,stroke:#000,color:#000\n style V0 fill:#69db7c,stroke:#000,color:#000\n style V1 fill:#69db7c,stroke:#000,color:#000\n style V2 fill:#69db7c,stroke:#000,color:#000\n style V3 fill:#69db7c,stroke:#000,color:#000\n style N0 fill:#00ceff,stroke:#000,color:#000\n style N1 fill:#00ceff,stroke:#000,color:#000\n style N2 fill:#00ceff,stroke:#000,color:#000\n style N3 fill:#00ceff,stroke:#000,color:#000\n style L0 fill:#38d9a9,stroke:#000,color:#000\n style L1 fill:#38d9a9,stroke:#000,color:#000\n style L2 fill:#38d9a9,stroke:#000,color:#000\n style L3 fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n\n| Approach | Pros | Cons | Use When |\n|----------|------|------|----------|\n| `defaultdict(list)` | Handles any node IDs, no wasted space | Slightly slower due to hashing | Node IDs are large, sparse, or non-numeric |\n| `[[] for _ in range(n)]` | Fast index access, no hashing overhead | Wastes space if node IDs are sparse | Nodes are 0 to n-1 |\n\n\n---\n\n# Iterating and Modifying Collections Safely\n\nModifying a dictionary or set while iterating over it causes a `RuntimeError`. Modifying a list during iteration does not raise an error, but it causes silent bugs as indices shift underneath you.\n\n### Dictionaries and Sets\n\n\n```python\n# WRONG: RuntimeError, dictionary changed size during iteration\nd = {'a': 1, 'b': 2, 'c': 3}\nfor key in d:\n if d[key] < 2:\n del d[key]\n\n# CORRECT: iterate over a copy of keys\nfor key in list(d.keys()):\n if d[key] < 2:\n del d[key]\n\n# CORRECT: build a new dict with comprehension\nd = {k: v for k, v in d.items() if v >= 2}\n```\n\n\nThe same applies to sets:\n\n\n```python\n# WRONG: RuntimeError\ns = {1, 2, 3, 4, 5}\nfor x in s:\n if x % 2 == 0:\n s.remove(x)\n\n# CORRECT: iterate over a copy\nfor x in list(s):\n if x % 2 == 0:\n s.remove(x)\n\n# CORRECT: set comprehension\ns = {x for x in s if x % 2 != 0}\n```\n\n\n### Lists\n\nModifying a list while iterating does not raise an error, but it causes subtle bugs because indices shift:\n\n\n```python\n# WRONG: skips elements because indices shift after removal\nlst = [1, 2, 3, 4, 5]\nfor i in range(len(lst)):\n if lst[i] % 2 == 0:\n lst.pop(i) # After removing index 1, index 2 becomes index 1\n\n# CORRECT: iterate backward\nfor i in range(len(lst) - 1, -1, -1):\n if lst[i] % 2 == 0:\n lst.pop(i)\n\n# CORRECT: build a new list (most Pythonic)\nlst = [x for x in lst if x % 2 != 0]\n```\n\n\nIn practice, most DSA problems do not require removing during iteration. You are far more likely to build a new collection with the desired elements.\n\n---\n\n# Deduplication Patterns\n\nMany DSA problems require avoiding duplicate results (e.g., 3Sum, 4Sum, permutations with duplicates). Python offers two approaches.\n\n### Sort and Skip Duplicates\n\nThis is the preferred approach for sorted array problems:\n\n\n```python\nnums.sort()\nfor i in range(len(nums)):\n # Skip duplicates: if this value is the same as the previous, skip it\n if i > 0 and nums[i] == nums[i - 1]:\n continue\n # Process nums[i]\n```\n\n\nThis runs in O(1) extra space (beyond the sort) and produces results in sorted order.\n\n### Set-Based Deduplication\n\nUse a set to collect unique results. Remember that lists are not hashable, so convert to tuples:\n\n\n```python\nresult_set = set()\n# ... generate candidates ...\nresult_set.add(tuple(sorted([a, b, c]))) # Must use tuple (hashable)\n\n# Convert back to list of lists for the final answer\nreturn [list(t) for t in result_set]\n```\n\n\nThe sort-and-skip approach is generally preferred in interviews because it avoids the overhead of hashing and produces cleaner code. But set-based deduplication is simpler to implement and is a valid fallback when the sort-and-skip logic is complex.\n\n---\n\n# Common DSA Idioms in Python\n\nThis section collects the small patterns and utilities that come up repeatedly across many problem types.\n\n### Sentinel Values\n\n\n```python\nmin_val = float('inf') # Positive infinity (for finding minimums)\nmax_val = float('-inf') # Negative infinity (for finding maximums)\n\n# Also available from math module\nfrom math import inf\nmin_val = inf\nmax_val = -inf\n```\n\n\n### Math Utilities\n\n\n```python\nmax(a, b) # Built-in maximum\nmin(a, b) # Built-in minimum\nabs(a) # Absolute value\npow(2, 10) # Power (also 2**10)\npow(base, exp, mod) # Modular exponentiation: built-in and efficient!\ndivmod(a, b) # Returns (a // b, a % b) in one call\n\nfrom math import isqrt, gcd, lcm, ceil, floor, log2\n\nisqrt(17) # 4 (integer square root, Python 3.8+)\ngcd(12, 8) # 4\nlcm(4, 6) # 12 (Python 3.9+)\nceil(7 / 2) # 4\nfloor(7 / 2) # 3\nlog2(8) # 3.0\n```\n\n\n### Ceiling Division Without Importing math\n\n\n```python\n# Integer ceiling division: ceil(a / b)\nresult = (a + b - 1) // b\n\n# This avoids floating-point issues that can occur with:\n# math.ceil(a / b) can lose precision for very large integers\n```\n\n\n### Deep Copy vs Shallow Copy\n\n\n```python\n# Shallow copy (one level deep)\ncopy1 = lst[:] # Slicing\ncopy2 = list(lst) # Constructor\ncopy3 = lst.copy() # Method\n\n# For 2D lists, shallow copy is NOT enough\nmatrix_copy = [row[:] for row in matrix] # Deep copy of 2D list\n\n# For arbitrarily nested structures\nimport copy\ndeep = copy.deepcopy(nested_structure)\n```\n\n\n### Type Conversions\n\n\n```python\n# List <-> Tuple\ntuple(my_list) # List to tuple (for hashability)\nlist(my_tuple) # Tuple to list (for mutability)\n\n# String <-> List of characters\nlist(\"hello\") # ['h', 'e', 'l', 'l', 'o']\n\"\".join(['h', 'e', 'l', 'l', 'o']) # \"hello\"\n\n# String <-> Integer\nint(\"42\") # 42\nstr(42) # \"42\"\nint(\"1010\", 2) # 10 (binary string to int)\nbin(10) # '0b1010' (int to binary string)\n\n# Set <-> List\nset(my_list) # Remove duplicates\nlist(my_set) # Convert back (order not guaranteed)\nsorted(my_set) # Sorted list from set\n```\n\n\n### Infinity and Comparison Tricks\n\n\n```python\n# float('inf') is greater than any number\nfloat('inf') > 10**100 # True\n\n# Useful for initializing distance/cost arrays\ndist = [float('inf')] * n\ndist[start] = 0\n\n# Chained comparisons\nif 0 <= x < n: # Same as: if x >= 0 and x < n\n ...\n\nif a <= b <= c: # Same as: if a <= b and b <= c\n ...\n```\n\n\n---\n\n# OOP Basics for Design Problems\n\nMany DSA problems use custom node classes. LeetCode typically defines these for you, but you should know the patterns:\n\n### Common Node Definitions\n\n\n```python\n# Linked List Node\nclass ListNode:\n def __init__(self, val=0, next=None):\n self.val = val\n self.next = next\n\n# Binary Tree Node\nclass TreeNode:\n def __init__(self, val=0, left=None, right=None):\n self.val = val\n self.left = left\n self.right = right\n\n# Trie Node\nclass TrieNode:\n def __init__(self):\n self.children = {} # Or [None] * 26 for lowercase letters only\n self.is_end = False\n\n# Graph Node (for problems like Clone Graph)\nclass Node:\n def __init__(self, val=0, neighbors=None):\n self.val = val\n self.neighbors = neighbors if neighbors is not None else []\n```\n\n\n### Custom Comparison for Heaps\n\nIf you need to put custom objects in a heap, define `__lt__` (less than):\n\n\n```python\nclass ListNode:\n def __init__(self, val=0, next=None):\n self.val = val\n self.next = next\n\n def __lt__(self, other):\n return self.val < other.val\n\n# Now you can push ListNode objects onto a heap\nheap = []\nheappush(heap, node1) # Compares using __lt__\nheappush(heap, node2)\nsmallest = heappop(heap)\n```\n\n\nAlternatively, use a tuple with a counter as a tie-breaker (as shown in the heapq section). The tuple approach is generally preferred because it does not require modifying the class definition.\n\n---\n\n# Performance Considerations\n\nPython is one of the slower languages used in competitive programming. LeetCode adjusts time limits per language, so this rarely matters in practice, but understanding common performance pitfalls helps you avoid unnecessary TLE (Time Limit Exceeded) verdicts.\n\n### Common Performance Pitfalls\n\n\n| Operation | Slow | Fast | Why |\n|-----------|------|------|-----|\n| BFS queue | `list.pop(0)` | `deque.popleft()` | O(n) vs O(1) |\n| String building | `s += char` in loop | `\"\".join(parts)` | O(n^2) vs O(n) |\n| Membership test | `x in list` | `x in set` | O(n) vs O(1) |\n| Insert at front | `list.insert(0, x)` | `deque.appendleft(x)` | O(n) vs O(1) |\n| Sorted insert | `insort(list, x)` | `SortedList.add(x)` | O(n) vs O(log n) |\n| Deep copy | `copy.deepcopy()` | `[row[:] for row in matrix]` | General vs specific |\n\n\n### Tips for Avoiding TLE in Python\n\n1. **Use the right data structure.** `set` for lookups, `deque` for BFS, `heapq` for priority queues.\n2. **Avoid unnecessary copies.** Slicing creates new lists. Use indices instead when possible.\n3. **Use **`@cache`** for memoization.** It is faster than a manual memo dictionary for most cases.\n4. **List comprehensions are faster than building a list with **`append`** in a loop.** They avoid the repeated attribute lookup of `.append` and use optimized bytecode.\n5. **Local variables are faster than global variables** in Python. If a function accesses a global frequently, assign it to a local variable first.\n6. **Avoid **`str += char`** in loops.** Use `\"\".join()`.\n7. **Use **`sys.setrecursionlimit` for deep recursion rather than converting to iteration (unless the depth is truly massive).","pageType":"dsa"}

Get Premium