{"title":"TypeScript Crash Course for DSA","description":"","content":"This chapter is a focused crash course on the TypeScript features used repeatedly in DSA and coding interview prep. 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# Built-in Data Structures\n\nTypeScript on LeetCode works like JavaScript with types bolted on. You do not need to import anything for the core data structures and utilities. Everything is globally available:\n\n\n| Built-in | What It Provides | DSA Use Case |\n|----------|-----------------|--------------|\n| `Array` | Dynamic array with rich methods | Primary data structure for everything |\n| `Map` | Hash map with any key type | Frequency counting, O(1) lookups |\n| `Set` | Hash set with any value type | Visited tracking, deduplication |\n| `Math` | `max`, `min`, `floor`, `ceil`, `abs`, `sqrt`, `log2` | Utility calculations |\n| `JSON` | `stringify`, `parse` | Deep copy, composite keys |\n| `Infinity` / `-Infinity` | Global sentinel values | Min/max initialization |\n\n\nBut TypeScript also has notable gaps. These are data structures needed in DSA with no built-in equivalent:\n\n\n| Not Built-in | What You Must Do |\n|--------------|------------------|\n| Queue | Use object with pointers, or linked list |\n| Deque | Use array (limited), or custom class |\n| PriorityQueue | Implement a min-heap yourself |\n| TreeMap / TreeSet | Sorted array + binary search (limited) |\n\n\nWe will cover typed implementations for each of these missing structures later in this chapter. What TypeScript does give you is clean, type-safe, and fast to write.\n\n---\n\n# Variables, Types, and the Number Type\n\nTypeScript is a statically typed superset of JavaScript. You declare types explicitly, or let the compiler infer them:\n\n\n```typescript\nlet count: number = 0; // explicit type annotation\nconst ratio = 3.14; // inferred as number\nconst name: string = \"hello\"; // string\nlet found: boolean = true; // boolean\nconst nothing: null = null; // null\nlet missing: undefined; // undefined\n```\n\n\nFor variable declarations, follow one rule: **use **`const`** by default, **`let`** when you need to reassign, never **`var`**.** The `var` keyword has function scope (not block scope), which leads to subtle bugs in loops and conditionals. Both `let` and `const` are block-scoped, which is what you expect.\n\n\n```typescript\n// var leaks out of blocks\nfor (var i = 0; i < 5; i++) { }\nconsole.log(i); // 5 (still accessible!)\n\n// let stays in its block\nfor (let j = 0; j < 5; j++) { }\n// console.log(j); // Error: j is not defined\n```\n\n\nFor DSA, a small set of types is enough:\n\n\n| Type | Example | DSA Use Case |\n|------|---------|--------------|\n| `number` | `42`, `3.14`, `Infinity` | Everything numeric (no separate int/float!) |\n| `string` | `\"hello\"` | Immutable character sequences |\n| `boolean` | `true`, `false` | Visited arrays, flags |\n| `null` | `null` | Intentional absence (tree/linked list terminators) |\n| `undefined` | `undefined` | Uninitialized variables, missing properties |\n| `bigint` | `42n` | Values exceeding 2^53 - 1 (rare in DSA) |\n\n\nTypeScript has no integer type. Every number is an IEEE 754 64-bit floating-point double, exactly like JavaScript. The number `42` and the number `42.0` are the same value, the same type, stored the same way.\n\nThis has three implications for DSA:\n\n**1. Division always produces a float.** In TypeScript, `7 / 2` gives `3.5`, not `3`. You must explicitly truncate when you need an integer:\n\n\n```typescript\n// Integer division in TypeScript\nMath.floor(7 / 2); // 3 (rounds toward negative infinity)\nMath.trunc(7 / 2); // 3 (rounds toward zero)\nMath.ceil(7 / 2); // 4 (rounds toward positive infinity)\n\n// For positive numbers, floor and trunc are the same\n// For negative numbers, they differ:\nMath.floor(-7 / 2); // -4 (rounds down)\nMath.trunc(-7 / 2); // -3 (rounds toward zero)\n```\n\n\n**2. Integer precision is limited to 2^53 - 1.** The `Number.MAX_SAFE_INTEGER` is 9,007,199,254,740,991. Beyond this, integer arithmetic loses precision without warning:\n\n\n```typescript\nconsole.log(9007199254740992 === 9007199254740993); // true! Both round to the same float\n```\n\n\nFor most DSA problems where constraints are up to 10^9, this is not an issue. If you truly need arbitrary precision, use `BigInt`:\n\n\n```typescript\nconst big: bigint = 9007199254740993n; // note the 'n' suffix\nconst result: bigint = big * 2n; // BigInt arithmetic\n// Cannot mix: big + 1 throws TypeError. Must use big + 1n\n```\n\n\n**3. Binary search midpoint does not overflow, but needs floor.** TypeScript numbers safely hold sums up to 2^53, so `(left + right)` will not overflow for typical DSA inputs. But you need `Math.floor` because division produces a float:\n\n\n```typescript\n// WRONG: produces a float when left + right is odd\nconst mid = (left + right) / 2;\n\n// CORRECT: floor to get integer index\nconst mid = Math.floor((left + right) / 2);\n```\n\n\nThe **ternary operator** works exactly as in other languages:\n\n\n```typescript\nconst result = (a > b) ? a : b; // Same as Math.max(a, b)\nconst label = (count === 1) ? \"item\" : \"items\";\n```\n\n\n---\n\n# Type Annotations and Inference\n\nTypeScript's type system catches bugs before you run your code, which matters in DSA where one off-by-one or null-handling mistake can fail a submission. Here is what you need to know.\n\n**When to annotate vs. let TypeScript infer:**\n\n\n```typescript\n// Inference works great for simple assignments\nconst count = 0; // inferred as number\nconst names = [\"a\", \"b\"]; // inferred as string[]\n\n// Annotate when the type is not obvious from the value\nlet result: number[] = []; // empty array needs annotation\nlet node: ListNode | null = head; // union type\nconst freq: Map = new Map(); // generic types\n```\n\n\n**Function signatures** should always be annotated. This is where type safety pays off most:\n\n\n```typescript\nfunction twoSum(nums: number[], target: number): number[] {\n const map = new Map();\n for (let i = 0; i < nums.length; i++) {\n const complement = target - nums[i];\n if (map.has(complement)) {\n return [map.get(complement)!, i];\n }\n map.set(nums[i], i);\n }\n return [];\n}\n```\n\n\nThe `!` after `map.get(complement)` is the **non-null assertion operator**. We already checked `map.has(complement)`, so we know the value exists, but TypeScript does not know that. The `!` tells the compiler \"trust me, this is not undefined.\" We will cover this in detail in the Null Handling section.\n\n**Array types** have two equivalent syntaxes:\n\n\n```typescript\nconst nums: number[] = [1, 2, 3]; // Preferred for simple types\nconst grid: number[][] = [[1, 2], [3, 4]]; // 2D array\nconst words: Array = [\"hello\"]; // Generic syntax (same thing)\n```\n\n\nUse `number[]` for simple types and `Array` when the element type is complex (like `Array<[number, number]>`).\n\n**Tuple types** are useful for DSA. Unlike plain arrays, tuples have fixed length and typed positions:\n\n\n```typescript\n// A tuple representing [row, col]\nconst cell: [number, number] = [3, 5];\n\n// Tuple with named elements (TypeScript 4.0+)\ntype Coordinate = [row: number, col: number];\nconst pos: Coordinate = [1, 2];\n\n// Tuple for BFS queue entries: [row, col, distance]\ntype BFSEntry = [number, number, number];\nconst entry: BFSEntry = [0, 0, 0];\n```\n\n\n**Union types** handle cases where a value can be one of several types:\n\n\n```typescript\n// Tree node can be a TreeNode or null\nlet current: TreeNode | null = root;\n\n// Function that returns a number or -1 for \"not found\"\nfunction indexOf(nums: number[], target: number): number {\n for (let i = 0; i < nums.length; i++) {\n if (nums[i] === target) return i;\n }\n return -1;\n}\n```\n\n\n**Type narrowing** is how TypeScript automatically refines a union type based on control flow:\n\n\n```typescript\nfunction process(node: TreeNode | null): number {\n if (node === null) return 0; // After this line, node is TreeNode (not null)\n return node.val + process(node.left) + process(node.right);\n}\n```\n\n\nThe compiler tracks which branches have already handled `null`, so you get full type safety without extra casts.\n\n---\n\n# Operators and Control Flow\n\nMost operators work exactly like JavaScript, but a few deserve special attention for DSA.\n\n### Strict Equality\n\n**Always use **`===`** and **`!==`** in TypeScript.** The `==` operator performs type coercion, which creates surprising results:\n\n\n```typescript\n0 == \"\" // true (empty string coerces to 0)\n0 == false // true (false coerces to 0)\nnull == undefined // true (special coercion rule)\n\"5\" == 5 // true (string coerces to number; TypeScript may warn about this)\n\n// With ===, none of these are true\n0 === \"\" // false\n0 === false // false\nnull === undefined // false\n```\n\n\nTypeScript's type system helps here. It will flag many invalid `==` comparisons as errors. But `===` is still the right habit.\n\n### Modular Arithmetic\n\nThe `%` operator appears in hashing, cyclic array problems, and math-heavy questions. Like JavaScript, TypeScript's `%` can return negative values for negative operands: `-7 % 3` gives `-1`, not `2`. To guarantee a positive result:\n\n\n```typescript\n((n % m) + m) % m // Always non-negative\n```\n\n\nMany problems ask you to return the result \"modulo 10^9 + 7\":\n\n\n```typescript\nconst MOD = 1_000_000_007; // Underscores for readability\n\nlet result = 0;\nfor (let i = 0; i < n; i++) {\n result = (result + values[i]) % MOD;\n}\nreturn result;\n```\n\n\n### Bitwise Operators\n\nBitwise operators convert their operands to 32-bit signed integers. This means they work correctly for values up to about 2 billion, but produce wrong results for larger numbers without warning:\n\n\n```typescript\n// Works fine for normal DSA values\nconst isSet = (mask & (1 << i)) !== 0; // Check if bit i is set\nconst setBit = mask | (1 << i); // Set bit i\nconst clearBit = mask & ~(1 << i); // Clear bit i\nconst toggleBit = mask ^ (1 << i); // Toggle bit i\n\n// XOR trick: find the number that appears once\nlet single = 0;\nfor (const num of nums) {\n single ^= num; // XOR cancels out duplicates\n}\n```\n\n\nThe key bitwise operators:\n\n\n| Operator | Symbol | DSA Use |\n|----------|--------|---------|\n| AND | `&` | Masking, checking if bit is set |\n| OR | `\\|` | Setting bits |\n| XOR | `^` | Finding unique elements, toggling |\n| NOT | `~` | Bit inversion |\n| Left shift | `<<` | Multiply by powers of 2: `1 << n` equals 2^n |\n| Right shift | `>>` | Signed right shift (preserves sign) |\n| Unsigned right shift | `>>>` | Unsigned right shift (fills with 0) |\n\n\n**Warning:** `1 << 31` gives `-2147483648` (negative!) because it sets the sign bit of a 32-bit integer. For bitmask problems with up to 20-25 elements, this is not a concern. For problems using all 32 bits, be careful.\n\n### Control Flow\n\nTypeScript offers three loop forms. Use each where it fits:\n\n\n```typescript\n// Index-based for: when you need the index\nfor (let i = 0; i < nums.length; i++) { ... }\n\n// Backward traversal (used in some DP and stack problems)\nfor (let i = n - 1; i >= 0; i--) { ... }\n\n// for-of: when you only need values\nfor (const num of nums) { ... }\n\n// While: when the termination condition is not index-based\nwhile (left < right) { ... }\n```\n\n\nOne limitation: the `for-of` loop does not give you the index. If you need both index and value, use `for` with an index or `nums.forEach((val, idx) => ...)`.\n\n### Nullish Coalescing and Optional Chaining\n\nThese two operators handle safe access in TypeScript:\n\n\n```typescript\n// Nullish coalescing: returns right side if left is null or undefined\nconst count = map.get(key) ?? 0; // 0 if key not found (get returns undefined)\n\n// Optional chaining: short-circuits to undefined if left is null/undefined\nconst leftVal = node?.left?.val; // undefined if node or node.left is null\n\n// Combining both: safe access with default\nconst val = node?.left?.val ?? 0;\n```\n\n\nThe `??` operator is different from `||`. The `||` operator treats `0`, `\"\"`, and `false` as falsy and returns the right side. The `??` operator only triggers on `null` and `undefined`. For frequency counting where 0 is a valid count, always use `??`.\n\n---\n\n# Functions, Scope, and Generics\n\nIn DSA problems on LeetCode, your solution is typically a function or a class method. TypeScript supports both regular functions and arrow functions:\n\n\n```typescript\n// Regular function with type annotations\nfunction maxDepth(root: TreeNode | null): number {\n if (!root) return 0;\n return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));\n}\n\n// Arrow function (common for helpers and callbacks)\nconst swap = (arr: number[], i: number, j: number): void => {\n [arr[i], arr[j]] = [arr[j], arr[i]];\n};\n```\n\n\n### Pass-by-Value with Reference Types\n\nTypeScript, like JavaScript, is always **pass-by-value**. But for objects (including arrays, Maps, Sets), the \"value\" is a reference. This means:\n\n- **Primitive parameters** are copies. Changing them inside a function does not affect the caller.\n- **Object/array parameters** pass a copy of the reference. You can modify the contents (like `arr[i] = 5`), but reassigning the reference itself does not affect the caller.\n\nThis is why backtracking works. You modify a shared array and undo the modification after recursion:\n\n\n```typescript\nfunction backtrack(path: number[], results: number[][]): void {\n if (isComplete(path)) {\n results.push([...path]); // MUST spread-copy, not push reference\n return;\n }\n for (const choice of choices) {\n path.push(choice); // Modify shared array\n backtrack(path, results); // Recurse\n path.pop(); // Undo modification\n }\n}\n```\n\n\nThe `[...path]` spread when saving results creates a copy. If you wrote `results.push(path)` instead, every entry in `results` would be a reference to the same array, and they would all end up empty after backtracking unwinds.\n\n### Generics\n\nGenerics let you write type-safe, reusable code:\n\n\n```typescript\n// Generic function: works with any array type\nfunction swap(arr: T[], i: number, j: number): void {\n [arr[i], arr[j]] = [arr[j], arr[i]];\n}\n\nswap([1, 2, 3], 0, 2); // T inferred as number\nswap([\"a\", \"b\", \"c\"], 0, 2); // T inferred as string\n```\n\n\nGenerics appear heavily in the Queue and MinHeap implementations later. For now, think of `` as \"this works for any type T.\"\n\n### Closures\n\nClosures capture variables from their enclosing scope. This is useful in DSA for creating comparators and memoization:\n\n\n```typescript\n// Closure capturing 'graph' from outer scope\nfunction dfs(node: number, visited: Set, graph: Map): void {\n visited.add(node);\n for (const neighbor of graph.get(node) ?? []) {\n if (!visited.has(neighbor)) {\n dfs(neighbor, visited, graph);\n }\n }\n}\n```\n\n\n---\n\n# Arrays\n\nArrays are the foundational data structure and the starting point for almost every DSA problem.\n\n\n```typescript\n// Declaration and initialization\nconst nums: number[] = [1, 2, 3, 4, 5];\nconst visited: boolean[] = new Array(n).fill(false);\nconst dp: number[] = new Array(n + 1).fill(0);\nconst grid: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(0));\n```\n\n\n**Array initialization matters.** There is a gotcha with 2D arrays:\n\n\n```typescript\n// WRONG: all rows share the same inner array reference!\nconst bad: number[][] = new Array(3).fill(new Array(3).fill(0));\nbad[0][0] = 1; // Changes ALL rows because they are the same array!\n\n// CORRECT: each row is a new array\nconst good: number[][] = Array.from({ length: 3 }, () => new Array(3).fill(0));\ngood[0][0] = 1; // Only changes row 0\n```\n\n\nThis is a common bug in matrix problems. `fill()` does not clone objects. It fills every slot with the same reference.\n\n**The **`.length`** property** gives the array size. TypeScript is consistent across arrays and strings:\n\n\n```typescript\nconst arr = [1, 2, 3];\narr.length; // 3 (property)\n\nconst s = \"hello\";\ns.length; // 5 (property)\n\n// Map and Set use .size instead\nconst map = new Map();\nmap.size; // 0 (property)\n```\n\n\n### 2D Arrays\n\n2D arrays appear in every matrix problem (BFS on grid, dynamic programming tables):\n\n\n```typescript\nconst matrix: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(0));\n\n// Access: matrix[row][col]\n// Row count: matrix.length\n// Column count: matrix[0].length\n```\n\n\nFor DP problems, you often need a table with one extra row and column for the base case:\n\n\n```typescript\nconst dp: number[] = new Array(n + 1).fill(0);\nconst dp2d: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));\n```\n\n\nThe 4-directional neighbor pattern is one of the most common patterns in matrix problems:\n\n\n```typescript\nconst directions: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];\n\nfor (const [dr, dc] of directions) {\n const newRow = row + dr;\n const newCol = col + dc;\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {\n // Process neighbor\n }\n}\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\n### Essential Array Methods\n\n\n```typescript\nconst arr: number[] = [1, 2, 3];\n\n// Adding and removing\narr.push(4); // Add to end: O(1) -> [1, 2, 3, 4]\narr.pop(); // Remove from end: O(1) -> [1, 2, 3]\narr.unshift(0); // Add to front: O(n) -> [0, 1, 2, 3]\narr.shift(); // Remove from front: O(n) -> [1, 2, 3]\n\n// Slicing and splicing\narr.slice(1, 3); // Copy subarray [1, 3): [2, 3] (does NOT modify original)\narr.splice(1, 1); // Remove 1 element at index 1: O(n) (MODIFIES original)\n\n// Searching\narr.indexOf(2); // First index of value, -1 if not found: O(n)\narr.includes(2); // Boolean membership check: O(n)\n\n// Utility\narr.reverse(); // Reverse in place\narr.fill(0); // Fill all elements with 0\narr.join(\",\"); // Join elements: \"1,2,3\"\n```\n\n\n**The spread operator** `...` is the standard way to copy and combine arrays:\n\n\n```typescript\nconst copy = [...arr]; // Shallow copy\nconst combined = [...arr1, ...arr2]; // Concatenate\nconst max = Math.max(...arr); // Spread into function arguments\nconst min = Math.min(...arr);\n```\n\n\n`Array.from()` creates arrays from iterables or with initialization logic:\n\n\n```typescript\n// Create array of indices\nconst indices = Array.from({ length: n }, (_, i) => i); // [0, 1, 2, ..., n-1]\n\n// Create 2D array\nconst grid = Array.from({ length: rows }, () => new Array(cols).fill(0));\n\n// Convert Set to Array\nconst arr = Array.from(mySet);\n// Or equivalently: const arr = [...mySet];\n```\n\n\n---\n\n# Strings\n\nStrings in TypeScript are **immutable**. Every time you \"modify\" a string, you create a new one. This has a performance implication:\n\n\n```typescript\n// BAD: O(n^2) because each += creates a new string\nlet result = \"\";\nfor (const c of chars) {\n result += c; // Creates a new string every iteration\n}\n\n// GOOD: O(n) with array join\nconst parts: string[] = [];\nfor (const c of chars) {\n parts.push(c);\n}\nconst result = parts.join(\"\");\n```\n\n\nTypeScript does not have a dedicated mutable string builder. The standard approach is to collect parts in an array and join at the end.\n\nCommon string methods:\n\n\n| Method | Returns | Example | DSA Use |\n|--------|---------|---------|---------|\n| `charAt(i)` or `[i]` | `string` | `s[0]` | Access individual characters |\n| `length` | `number` | `s.length` | Loop bounds (property, no parentheses) |\n| `substring(start, end)` | `string` | `s.substring(0, 3)` | Extract portions (end exclusive) |\n| `slice(start, end)` | `string` | `s.slice(0, 3)` | Same as substring, supports negative indices |\n| `split(sep)` | `string[]` | `s.split(\" \")` | Tokenize strings |\n| `indexOf(str)` | `number` | `s.indexOf(\"ab\")` | Find substrings (-1 if not found) |\n| `includes(str)` | `boolean` | `s.includes(\"ab\")` | Substring check |\n| `startsWith(prefix)` | `boolean` | `s.startsWith(\"ab\")` | Prefix check |\n| `endsWith(suffix)` | `boolean` | `s.endsWith(\"ab\")` | Suffix check |\n| `trim()` | `string` | `s.trim()` | Remove leading/trailing whitespace |\n| `toLowerCase()` | `string` | `s.toLowerCase()` | Case conversion |\n| `toUpperCase()` | `string` | `s.toUpperCase()` | Case conversion |\n| `repeat(n)` | `string` | `\"ab\".repeat(3)` | `\"ababab\"` |\n\n\n**Template literals** let you embed expressions in strings, which is useful for creating composite Map keys:\n\n\n```typescript\n// Composite key for a grid cell\nconst key = `${row},${col}`;\nvisited.add(key);\n\n// Composite key for a state in BFS\nconst state = `${row},${col},${direction}`;\n```\n\n\n### Character Utilities\n\nTypeScript does not have a separate `char` type. Characters are single-character strings. To work with character codes, use `charCodeAt` and `String.fromCharCode`:\n\n\n```typescript\nconst code = \"a\".charCodeAt(0); // 97\nconst char = String.fromCharCode(97); // \"a\"\n\n// Map 'a'-'z' to 0-25 (frequency arrays)\nconst index = s.charCodeAt(i) - \"a\".charCodeAt(0);\n\n// Map 0-25 back to 'a'-'z'\nconst char = String.fromCharCode(\"a\".charCodeAt(0) + index);\n\n// Check if character is alphanumeric\nconst isAlphaNum = (c: string): boolean => /^[a-zA-Z0-9]$/.test(c);\n\n// Check if character is a digit\nconst isDigit = (c: string): boolean => c >= \"0\" && c <= \"9\";\n\n// Check if character is a letter\nconst isLetter = (c: string): boolean => /^[a-zA-Z]$/.test(c);\n```\n\n\nThe frequency array pattern using character codes:\n\n\n```typescript\n// Frequency array for lowercase letters (26 slots)\nconst freq: number[] = new Array(26).fill(0);\nconst aCode = \"a\".charCodeAt(0);\nfor (const c of s) {\n freq[c.charCodeAt(0) - aCode]++;\n}\n// freq[0] = count of 'a', freq[1] = count of 'b', etc.\n```\n\n\nThis is faster and more memory-efficient than `Map` when you know the character set is limited to lowercase (or uppercase, or digits).\n\n---\n\n# Collections: Map, Set, and Record\n\nChoosing the right collection is often the difference between an O(n) and an O(n^2) solution. TypeScript inherits JavaScript's collections but adds type safety through generics.\n\n\n```mermaid\nflowchart TD\n BUILT[\"Built-in Collections\"]\n ARR[\"Array<T>\"]\n MAP[\"Map<K, V>\"]\n SET[\"Set<T>\"]\n OBJ[\"Record<K, V>
(typed objects)\"]\n MISSING[\"Must Implement\"]\n Q[\"Queue<T>\"]\n PQ[\"MinHeap<T>\"]\n TM[\"TreeMap /
TreeSet\"]\n\n BUILT --> ARR\n BUILT --> MAP\n BUILT --> SET\n BUILT --> OBJ\n MISSING --> Q\n MISSING --> PQ\n MISSING --> TM\n\n style BUILT fill:#00ceff,stroke:#000,color:#000\n style ARR fill:#38d9a9,stroke:#000,color:#000\n style MAP fill:#38d9a9,stroke:#000,color:#000\n style SET fill:#38d9a9,stroke:#000,color:#000\n style OBJ fill:#38d9a9,stroke:#000,color:#000\n style MISSING fill:#ffa94d,stroke:#000,color:#000\n style Q fill:#ff8787,stroke:#000,color:#000\n style PQ fill:#ff8787,stroke:#000,color:#000\n style TM fill:#ff8787,stroke:#000,color:#000\n```\n\n\n### Map: The HashMap Equivalent\n\nES6 `Map` with TypeScript generics gives you a type-safe hash map with O(1) average-case operations:\n\n\n```typescript\nconst freq = new Map();\n\n// Frequency counting (most common Map pattern)\nfor (const c of s) {\n freq.set(c, (freq.get(c) ?? 0) + 1);\n}\n\n// Key operations\nfreq.has(\"a\"); // Check if key exists: O(1)\nfreq.get(\"a\"); // Get value (returns undefined if missing): O(1)\nfreq.set(\"a\", 5); // Set value: O(1)\nfreq.delete(\"a\"); // Remove key: O(1)\nfreq.size; // Number of entries (property, not method!)\nfreq.clear(); // Remove all entries\n\n// Iteration (insertion order is preserved)\nfor (const [key, value] of freq) { /* key-value pairs */ }\nfor (const key of freq.keys()) { /* keys only */ }\nfor (const value of freq.values()) { /* values only */ }\n```\n\n\n**A critical type safety point:** `map.get(key)` returns `V | undefined` in TypeScript. The compiler forces you to handle the missing-key case explicitly:\n\n\n```typescript\n// TypeScript error: Type 'number | undefined' is not assignable to 'number'\nconst count: number = freq.get(\"a\");\n\n// Fix 1: nullish coalescing\nconst count: number = freq.get(\"a\") ?? 0;\n\n// Fix 2: non-null assertion (only when you KNOW the key exists)\nconst count: number = freq.get(\"a\")!;\n```\n\n\n### Set: The HashSet Equivalent\n\n\n```typescript\nconst visited = new Set();\n\nvisited.add(node); // Add element: O(1)\nvisited.has(node); // Check membership: O(1)\nvisited.delete(node); // Remove element: O(1)\nvisited.size; // Number of elements\n\n// Create from array (deduplication!)\nconst unique = new Set(nums);\nconst uniqueArr = [...new Set(nums)]; // Back to array\n\n// Iteration\nfor (const val of visited) { /* values */ }\n```\n\n\n**Important:** Sets use reference equality for objects and arrays. `new Set([[1,2], [1,2]])` has size 2, not 1, because the two `[1,2]` arrays are different objects. For composite keys, serialize to strings:\n\n\n```typescript\nconst visited = new Set();\nvisited.add(`${row},${col}`); // Use template literal as key\nvisited.has(`${newRow},${newCol}`); // Check membership\n```\n\n\n### Record Type\n\nTypeScript's `Record` type creates typed plain objects, useful as lightweight maps with string keys:\n\n\n```typescript\n// Record is equivalent to { [key: string]: number }\nconst freq: Record = {};\nfor (const c of s) {\n freq[c] = (freq[c] ?? 0) + 1;\n}\n\n// Check existence\nif (c in freq) { /* exists */ }\nif (freq[c] !== undefined) { /* exists */ }\n\n// Iterate\nfor (const key of Object.keys(freq)) { /* keys */ }\nfor (const [key, value] of Object.entries(freq)) { /* key-value pairs */ }\n```\n\n\nUse `Map` as your default. Use `Record` only when you need a quick string-keyed frequency map and want concise code.\n\n### Queue Implementation (Typed)\n\nTypeScript has no built-in queue with O(1) dequeue. A typed implementation using an object as a sparse array with head/tail pointers:\n\n\n```typescript\nclass Queue {\n private items: Record = {};\n private head = 0;\n private tail = 0;\n\n enqueue(val: T): void {\n this.items[this.tail++] = val;\n }\n\n dequeue(): T | undefined {\n if (this.isEmpty()) return undefined;\n const val = this.items[this.head];\n delete this.items[this.head++];\n return val;\n }\n\n peek(): T | undefined {\n return this.items[this.head];\n }\n\n get size(): number {\n return this.tail - this.head;\n }\n\n isEmpty(): boolean {\n return this.tail === this.head;\n }\n}\n```\n\n\nBFS using this queue:\n\n\n```typescript\nfunction bfs(graph: Map, start: number): void {\n const visited = new Set([start]);\n const queue = new Queue();\n queue.enqueue(start);\n\n while (!queue.isEmpty()) {\n const node = queue.dequeue()!;\n for (const neighbor of graph.get(node) ?? []) {\n if (!visited.has(neighbor)) {\n visited.add(neighbor);\n queue.enqueue(neighbor);\n }\n }\n }\n}\n```\n\n\nFor level-order traversal, capture the queue size at the start of each level:\n\n\n```typescript\nlet level = 0;\nwhile (!queue.isEmpty()) {\n const levelSize = queue.size; // Capture before processing\n for (let i = 0; i < levelSize; i++) {\n const node = queue.dequeue()!;\n // ... process node, enqueue children\n }\n level++;\n}\n```\n\n\n### PriorityQueue / MinHeap (Typed)\n\nTypeScript has no built-in priority queue. For problems like top-K elements, Dijkstra's algorithm, or merge-K-sorted-lists, you need a min-heap. A generic typed implementation:\n\n\n```typescript\nclass MinHeap {\n private heap: T[] = [];\n private compare: (a: T, b: T) => number;\n\n constructor(compareFn: (a: T, b: T) => number = (a: any, b: any) => a - b) {\n this.compare = compareFn;\n }\n\n push(val: T): void {\n this.heap.push(val);\n this.siftUp(this.heap.length - 1);\n }\n\n pop(): T | undefined {\n if (this.heap.length === 0) return undefined;\n const top = this.heap[0];\n const last = this.heap.pop()!;\n if (this.heap.length > 0) {\n this.heap[0] = last;\n this.siftDown(0);\n }\n return top;\n }\n\n peek(): T | undefined {\n return this.heap[0];\n }\n\n get size(): number {\n return this.heap.length;\n }\n\n isEmpty(): boolean {\n return this.heap.length === 0;\n }\n\n private siftUp(i: number): void {\n while (i > 0) {\n const parent = Math.floor((i - 1) / 2);\n if (this.compare(this.heap[i], this.heap[parent]) >= 0) break;\n [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];\n i = parent;\n }\n }\n\n private siftDown(i: number): void {\n const n = this.heap.length;\n while (true) {\n let smallest = i;\n const left = 2 * i + 1;\n const right = 2 * i + 2;\n if (left < n && this.compare(this.heap[left], this.heap[smallest]) < 0) smallest = left;\n if (right < n && this.compare(this.heap[right], this.heap[smallest]) < 0) smallest = right;\n if (smallest === i) break;\n [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];\n i = smallest;\n }\n }\n}\n```\n\n\nUsage:\n\n\n```typescript\n// Min-heap of numbers (default)\nconst minHeap = new MinHeap();\nminHeap.push(5);\nminHeap.push(2);\nminHeap.push(8);\nminHeap.pop(); // 2\n\n// Max-heap (reverse comparator)\nconst maxHeap = new MinHeap((a, b) => b - a);\n\n// Custom objects: sort by distance, then by node ID\nconst heap = new MinHeap<[number, number]>((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);\nheap.push([5, 3]); // [distance, nodeId]\nheap.push([2, 1]);\nheap.pop(); // [2, 1]\n```\n\n\n### No TreeMap / TreeSet\n\nTypeScript has no sorted map or sorted set. This is a genuine disadvantage for problems that need:\n\n- Finding the floor/ceiling of a key (nearest smaller/larger)\n- Range queries on keys\n- Maintaining elements in sorted order with O(log n) insertions\n\nWorkarounds:\n\n1. **Sorted array + binary search:** Maintain a sorted array and use binary search for lookups. Insertion is O(n) due to shifting, but works for small datasets.\n2. **Sort when needed:** If you only need sorted access at the end, collect elements and sort once.\n3. **Accept the limitation:** In a TypeScript interview, mention the missing data structure and discuss the trade-off.\n\n### Collections Quick Reference\n\n\n| Collection | Type | Key Methods | Time Complexity | DSA Use |\n|------------|------|-------------|-----------------|---------|\n| `Array` | Dynamic array | `push`, `pop`, `shift`, `splice`, `slice`, `sort` | push/pop O(1), shift O(n), access O(1) | Stacks, results, DP tables |\n| `Map` | Hash map | `set`, `get`, `has`, `delete`, `size` | O(1) average | Frequency counting, two-sum |\n| `Set` | Hash set | `add`, `has`, `delete`, `size` | O(1) average | Visited tracking, dedup |\n| `Record` | Typed object | bracket access, `in`, `Object.keys` | O(1) average | Simple frequency maps |\n| `Queue` (custom) | FIFO queue | `enqueue`, `dequeue`, `peek`, `size` | O(1) all | BFS |\n| `MinHeap` (custom) | Priority queue | `push`, `pop`, `peek`, `size` | O(log n) push/pop | Top-K, Dijkstra |\n\n\n---\n\n# Sorting and Comparators\n\nSorting is a prerequisite for many algorithms: binary search, two pointers on sorted arrays, merge intervals, and greedy approaches.\n\n**JavaScript and TypeScript's default sort behavior:** `Array.sort()` converts elements to strings and sorts lexicographically by default:\n\n\n```typescript\nconst nums = [10, 9, 2, 21, 3];\nnums.sort(); // [10, 2, 21, 3, 9] (WRONG! Lexicographic order)\nnums.sort((a, b) => a - b); // [2, 3, 9, 10, 21] (correct numeric sort)\n```\n\n\n\n```typescript\n// Sort ascending\nnums.sort((a, b) => a - b);\n\n// Sort descending\nnums.sort((a, b) => b - a);\n\n// Sort intervals by start time (merge intervals pattern)\nconst intervals: number[][] = [[1,3], [2,6], [8,10]];\nintervals.sort((a, b) => a[0] - b[0]);\n\n// Sort strings by length, then alphabetically for ties\nwords.sort((a, b) => {\n if (a.length !== b.length) return a.length - b.length;\n return a.localeCompare(b);\n});\n\n// Sort by multiple keys: sort people by height desc, then name asc\nconst people: [string, number][] = [[\"Alice\", 170], [\"Bob\", 180], [\"Carol\", 170]];\npeople.sort((a, b) => b[1] !== a[1] ? b[1] - a[1] : a[0].localeCompare(b[0]));\n```\n\n\nNote that `Array.sort()` modifies the array in place and returns the same array. If you need to preserve the original, spread first:\n\n\n```typescript\nconst sorted = [...nums].sort((a, b) => a - b); // Original unchanged\n```\n\n\n**Important:** Since ES2019, `Array.sort()` is required by spec to be stable, and all modern engines (V8, SpiderMonkey, JavaScriptCore) comply. You can rely on stability on LeetCode and in any current Node version.\n\n---\n\n# Functional Patterns for DSA\n\nTypeScript inherits JavaScript's functional array methods. These make DSA code concise, but use them with awareness of their performance characteristics:\n\n\n```typescript\nconst nums = [1, 2, 3, 4, 5];\n\n// map: transform each element\nconst doubled = nums.map(x => x * 2); // [2, 4, 6, 8, 10]\n\n// filter: keep elements matching condition\nconst evens = nums.filter(x => x % 2 === 0); // [2, 4]\n\n// reduce: accumulate a single value\nconst sum = nums.reduce((acc, x) => acc + x, 0); // 15\n\n// find: first element matching condition (undefined if not found)\nconst firstEven = nums.find(x => x % 2 === 0); // 2\n\n// some: true if ANY element matches\nconst hasNegative = nums.some(x => x < 0); // false\n\n// every: true if ALL elements match\nconst allPositive = nums.every(x => x > 0); // true\n\n// forEach: iterate with side effects (no return value)\nnums.forEach((val, idx) => { /* access both value and index */ });\n\n// flat: flatten nested arrays\nconst nested = [[1, 2], [3, 4]];\nnested.flat(); // [1, 2, 3, 4]\n```\n\n\n**Performance note:** Each of these methods creates a new array (except `forEach`, `some`, `every`, and `find`). Chaining `.filter().map()` creates two intermediate arrays. In hot inner loops processing millions of elements, a plain `for` loop is faster. For most DSA problems, the difference is negligible.\n\n---\n\n# Null, Undefined, and Strict Null Checks\n\nTypeScript distinguishes between `null` and `undefined`, and its type system helps you handle both safely.\n\n**The difference:**\n\n- `undefined` means \"not assigned.\" It is the default value for uninitialized variables, missing object properties, and `Map.get()` for missing keys.\n- `null` means \"intentionally absent.\" You use it explicitly to represent \"no node\" in trees and linked lists.\n\nIn DSA, you encounter null/undefined primarily in three situations: tree/linked list problems, map lookups, and optional function parameters.\n\n**Rule 1: Use union types to express nullability.**\n\n\n```typescript\n// Tree traversal: node can be null\nfunction inorder(node: TreeNode | null): number[] {\n if (node === null) return [];\n return [...inorder(node.left), node.val, ...inorder(node.right)];\n}\n\n// Linked list: head can be null\nfunction reverseList(head: ListNode | null): ListNode | null {\n let prev: ListNode | null = null;\n let curr = head;\n while (curr !== null) {\n const next = curr.next;\n curr.next = prev;\n prev = curr;\n curr = next;\n }\n return prev;\n}\n```\n\n\n**Rule 2: Use nullish coalescing (**`??`**) for safe defaults.**\n\n\n```typescript\n// Safe map access\nconst count = freq.get(key) ?? 0;\n\n// Safe graph neighbor access\nconst neighbors = graph.get(node) ?? [];\n```\n\n\n**Rule 3: Use the non-null assertion (**`!`**) sparingly and only when you are certain.**\n\n\n```typescript\n// We just checked .has(), so .get() will not return undefined\nif (map.has(key)) {\n const val = map.get(key)!;\n}\n\n// After dequeue, we know queue was not empty\nwhile (!queue.isEmpty()) {\n const node = queue.dequeue()!;\n}\n```\n\n\n**Rule 4: Use optional chaining (**`?.`**) for safe property access.**\n\n\n```typescript\nconst leftVal = node?.left?.val; // undefined if node or left is null\nconst firstNeighbor = graph.get(node)?.[0]; // undefined if no neighbors\n```\n\n\n---\n\n# Iterating and Modifying Collections Safely\n\nTypeScript does not throw errors when you modify a collection during iteration. But that does not mean it is safe. The behavior is well-defined but easy to get wrong, and it produces bugs that are hard to track down.\n\n\n```typescript\n// DANGEROUS: modifying array while iterating with for-of\nconst arr = [1, 2, 3, 4, 5];\nfor (const num of arr) {\n if (num % 2 === 0) {\n arr.splice(arr.indexOf(num), 1); // Skips elements!\n }\n}\n// arr might be [1, 3, 5] or something unexpected\n```\n\n\nSafe alternatives:\n\n\n```typescript\n// Option 1: Filter into a new array (preferred)\nconst odds = arr.filter(num => num % 2 !== 0);\n\n// Option 2: Iterate backward with index-based loop\nfor (let i = arr.length - 1; i >= 0; i--) {\n if (arr[i] % 2 === 0) {\n arr.splice(i, 1);\n }\n}\n\n// Option 3: Collect indices to remove, then remove in reverse\nconst toRemove: number[] = [];\nfor (let i = 0; i < arr.length; i++) {\n if (arr[i] % 2 === 0) toRemove.push(i);\n}\nfor (let i = toRemove.length - 1; i >= 0; i--) {\n arr.splice(toRemove[i], 1);\n}\n```\n\n\nFor Maps and Sets, deleting during `for-of` iteration is safe per the ES6 specification. But adding new elements during iteration may or may not be visited, so avoid it:\n\n\n```typescript\n// Safe: delete from Map during iteration\nfor (const [key, value] of map) {\n if (value === 0) map.delete(key); // Defined behavior\n}\n\n// Dangerous: adding to Map during iteration\nfor (const [key, value] of map) {\n map.set(key + \"_copy\", value); // May or may not iterate over new entry\n}\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# Recursion and the Call Stack\n\nRecursion is the backbone of tree traversal, graph DFS, backtracking, and divide-and-conquer. Understanding how TypeScript handles recursion matters for these problems.\n\nEvery function call goes on the **call stack**, which has limited space. If your recursion goes too deep, you get a `RangeError: Maximum call stack size exceeded`:\n\n\n```typescript\n// This will crash for large n (V8's call-stack limit is around 10,000 to 15,000 frames)\nfunction factorial(n: number): number {\n if (n <= 1) return 1;\n return n * factorial(n - 1);\n}\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 > 5,000-10,000 |\n| Backtracking (k choices, depth d) | O(d) | Usually safe (d is small) |\n| DFS on graph (n nodes) | O(n) | Dangerous for large n |\n\n\n**The fix:** Convert deep recursion to an iterative approach using an explicit stack:\n\n\n```typescript\n// Recursive DFS (risks stack overflow for deep graphs)\nfunction dfs(node: number, visited: Set, graph: Map): void {\n visited.add(node);\n for (const neighbor of graph.get(node) ?? []) {\n if (!visited.has(neighbor)) dfs(neighbor, visited, graph);\n }\n}\n\n// Iterative DFS (safe for any depth)\nfunction dfsIterative(start: number, visited: Set, graph: Map): void {\n const stack: number[] = [start];\n while (stack.length > 0) {\n const node = stack.pop()!;\n if (visited.has(node)) continue;\n visited.add(node);\n for (const neighbor of graph.get(node) ?? []) {\n if (!visited.has(neighbor)) stack.push(neighbor);\n }\n }\n}\n```\n\n\nNote that TypeScript (and JavaScript) does **not** optimize tail recursion in practice. While the ES2015 spec defines proper tail calls, only Safari (JavaScriptCore) implements them. Node.js and V8 do not. If your recursion depth is proportional to input size and the input can be large, convert to iteration.\n\n---\n\n# Graph Representation Patterns\n\nGraphs appear in a large portion of DSA problems. TypeScript does not have a built-in graph class, so you need to build representations yourself. There are two common approaches:\n\n**Approach 1: Adjacency list with **`Array`**.** Use this when nodes are numbered 0 to n-1.\n\n\n```typescript\nconst n = 5;\nconst graph: number[][] = Array.from({ length: n }, () => []);\n\n// Add edges\nfor (const [u, v] of edges) {\n graph[u].push(v);\n graph[v].push(u); // Omit for directed graphs\n}\n\n// Access neighbors\nfor (const neighbor of graph[node]) { ... }\n```\n\n\n**Approach 2: Adjacency list with **`Map`**.** Use this when node IDs are not contiguous or are very large.\n\n\n```typescript\nconst graph = new Map();\n\nfor (const [u, v] of edges) {\n if (!graph.has(u)) graph.set(u, []);\n if (!graph.has(v)) graph.set(v, []);\n graph.get(u)!.push(v);\n graph.get(v)!.push(u);\n}\n\n// Access neighbors (with safety)\nfor (const neighbor of graph.get(node) ?? []) { ... }\n```\n\n\n**Weighted graphs** use tuples to store neighbor and weight:\n\n\n```typescript\n// Adjacency list for weighted graph\nconst graph: [number, number][][] = Array.from({ length: n }, () => []);\n\ngraph[from].push([to, weight]);\n\n// Used in Dijkstra:\nconst heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);\nheap.push([0, startNode]); // [distance, node]\n```\n\n\n\n```mermaid\nflowchart LR\n subgraph AdjList[\"Adjacency List (Array of Arrays)\"]\n N0[\"Node 0\"] --> L0[\"[1, 2]\"]\n N1[\"Node 1\"] --> L1[\"[0, 3]\"]\n N2[\"Node 2\"] --> L2[\"[0, 3]\"]\n N3[\"Node 3\"] --> L3[\"[1, 2]\"]\n end\n\n subgraph AdjMap[\"Adjacency Map (Map)\"]\n K0[\"Key: 0\"] --> V0[\"[1, 2]\"]\n K1[\"Key: 1\"] --> V1[\"[0, 3]\"]\n K2[\"Key: 2\"] --> V2[\"[0, 3]\"]\n K3[\"Key: 3\"] --> V3[\"[1, 2]\"]\n end\n\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 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```\n\n\n\n| Approach | Pros | Cons | Use When |\n|----------|------|------|----------|\n| `Array` | Fast index access, no hashing overhead | Wastes space if node IDs are sparse | Nodes are 0 to n-1 |\n| `Map` | Handles any node IDs, no wasted space | Slightly slower due to hashing | Node IDs are large, sparse, or non-numeric |\n\n\n---\n\n# Tuple and Pair Alternatives\n\nTypeScript does not have a built-in `tuple` at runtime. But its type system lets you type arrays as tuples, which gives you fixed-length, typed positions:\n\n**Option 1: TypeScript tuple types (preferred for typed code)**\n\n\n```typescript\n// BFS entry: [row, col]\nconst cell: [number, number] = [3, 5];\n\n// BFS with distance: [row, col, distance]\nconst entry: [number, number, number] = [0, 0, 0];\n\n// Queue of tuples\nconst queue = new Queue<[number, number]>();\nqueue.enqueue([startRow, startCol]);\n\n// Destructuring\nconst [r, c] = queue.dequeue()!;\n```\n\n\n**Option 2: Plain arrays (when you want flexibility)**\n\n\n```typescript\nconst cell = [row, col]; // Inferred as number[] (not tuple)\nconst r = cell[0];\nconst c = cell[1];\n```\n\n\n**Option 3: Interface (when clarity matters)**\n\n\n```typescript\ninterface Cell {\n row: number;\n col: number;\n dist: number;\n}\nconst entry: Cell = { row: 0, col: 0, dist: 0 };\n```\n\n\nIn practice, typed tuples `[number, number]` are the standard approach in TypeScript DSA. They combine type safety with conciseness.\n\n---\n\n# Deduplication Patterns\n\nMany DSA problems require avoiding duplicate results (e.g., 3Sum, 4Sum, permutations with duplicates). TypeScript offers two approaches:\n\n**Approach 1: Sort and skip duplicates (preferred for sorted array problems)**\n\n\n```typescript\nnums.sort((a, b) => a - b);\nfor (let i = 0; i < nums.length; i++) {\n // Skip duplicates: if this value is the same as the previous, skip it\n if (i > 0 && nums[i] === nums[i - 1]) continue;\n // Process nums[i]\n}\n```\n\n\nThis is the standard approach for problems like 3Sum and 4Sum. It runs in O(1) extra space (beyond the sort) and produces results in sorted order.\n\n**Approach 2: Use a Set to collect unique results**\n\n\n```typescript\nconst resultSet = new Set();\n// ... generate candidates ...\nresultSet.add(JSON.stringify([a, b, c])); // Serialize for uniqueness\nconst results = [...resultSet].map(s => JSON.parse(s) as number[]);\n```\n\n\nSince Sets compare objects by reference, you must serialize (e.g., `JSON.stringify`) to detect duplicate arrays. This is slower than the sort-and-skip approach but simpler to implement.\n\n---\n\n# Common DSA Idioms in TypeScript\n\nCommon small patterns and utility calls:\n\n**Swapping elements** (TypeScript's destructuring makes this clean):\n\n\n```typescript\n[arr[i], arr[j]] = [arr[j], arr[i]];\n\n// Or for variables:\n[a, b] = [b, a];\n```\n\n\n**Sentinel values** for tracking min/max:\n\n\n```typescript\nlet minVal = Infinity;\nlet maxVal = -Infinity;\nfor (const num of nums) {\n minVal = Math.min(minVal, num);\n maxVal = Math.max(maxVal, num);\n}\n```\n\n\n`Infinity` and `-Infinity` are globally available. They compare correctly with any number: `Infinity > 1e18` is `true`.\n\n**Math utilities:**\n\n\n```typescript\nMath.max(a, b); // Larger of two values\nMath.min(a, b); // Smaller of two values\nMath.abs(a); // Absolute value\nMath.pow(2, 10); // Power (also: 2 ** 10)\nMath.sqrt(n); // Square root\nMath.log2(n); // Log base 2\nMath.floor(a / b); // Floor division\nMath.ceil(a / b); // Ceiling division\n```\n\n\n**Ceiling division** without floating point:\n\n\n```typescript\n// Integer ceiling division: ceil(a / b) for positive a, b\nconst ceil = Math.floor((a + b - 1) / b);\n// Or equivalently:\nconst ceil = Math.floor((a - 1) / b) + 1;\n```\n\n\n**Type conversions:**\n\n\n```mermaid\nflowchart LR\n ARR[\"number[]\"]\n SET[\"Set<number>\"]\n STR[\"string\"]\n NUM[\"number\"]\n CARR[\"char (string)\"]\n\n ARR -->|\"new Set(arr)\"| SET\n SET -->|\"[...set]\"| ARR\n STR -->|\"Number(s) or +s\"| NUM\n NUM -->|\"String(n) or n.toString()\"| STR\n STR -->|\"s.split('')\"| ARR\n ARR -->|\"arr.join('')\"| STR\n\n style ARR fill:#00ceff,stroke:#000,color:#000\n style SET fill:#00ceff,stroke:#000,color:#000\n style STR fill:#ffa94d,stroke:#000,color:#000\n style NUM fill:#69db7c,stroke:#000,color:#000\n style CARR fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n\n```typescript\n// number <-> string\nconst num = Number(\"42\"); // 42\nconst num2 = parseInt(\"42\", 10); // 42 (always pass radix!)\nconst str = String(42); // \"42\"\nconst str2 = (42).toString(); // \"42\"\nconst str3 = (42).toString(2); // \"101010\" (binary representation)\n\n// string <-> array of characters\nconst chars = s.split(\"\"); // [\"h\", \"e\", \"l\", \"l\", \"o\"]\nconst str = chars.join(\"\"); // \"hello\"\n\n// Array <-> Set\nconst set = new Set(arr); // Array to Set\nconst arr = [...set]; // Set to Array\n\n// Deep copy (for simple objects/arrays)\nconst copy = JSON.parse(JSON.stringify(obj)); // Works but slow\nconst copy2 = structuredClone(obj); // Modern alternative (Node 17+)\n```\n\n\n`parseInt`** always needs a radix.** Without one, `parseInt(\"0x10\")` parses as hex (`16`), which can produce surprising results when the input comes from user data. Modern engines (ES5+) treat a leading `0` as decimal, but the explicit radix is still required by most lint rules:\n\n\n```typescript\nparseInt(\"42\", 10); // 42\nparseInt(\"08\", 10); // 8\nparseInt(\"0x10\", 10); // 0 (without radix this would parse as 16)\n```\n\n\n**Deep copy vs shallow copy:**\n\n\n```typescript\n// Shallow copy (array)\nconst copy = [...arr]; // New array, same element references\nconst copy2 = arr.slice(); // Same thing\n\n// Shallow copy (object)\nconst copy = { ...obj };\n\n// Deep copy (when elements are objects)\nconst deepCopy = JSON.parse(JSON.stringify(arr)); // Handles nested structures\n// Or for 2D arrays:\nconst grid2 = grid.map(row => [...row]); // Copy each inner array\n```\n\n\n---\n\n# OOP Basics for Design Problems\n\nDSA problems often define custom node classes. TypeScript classes give you type-safe definitions with clean syntax:\n\n\n```typescript\n// Linked list node\nclass ListNode {\n val: number;\n next: ListNode | null;\n\n constructor(val: number = 0, next: ListNode | null = null) {\n this.val = val;\n this.next = next;\n }\n}\n\n// Binary tree node\nclass TreeNode {\n val: number;\n left: TreeNode | null;\n right: TreeNode | null;\n\n constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {\n this.val = val;\n this.left = left;\n this.right = right;\n }\n}\n\n// Trie node\nclass TrieNode {\n children: Map;\n isEndOfWord: boolean;\n\n constructor() {\n this.children = new Map();\n this.isEndOfWord = false;\n }\n}\n\n// Graph node with neighbors\nclass GraphNode {\n val: number;\n neighbors: GraphNode[];\n\n constructor(val: number = 0, neighbors: GraphNode[] = []) {\n this.val = val;\n this.neighbors = neighbors;\n }\n}\n```\n\n\nTypeScript also supports a **shorthand constructor** syntax that reduces boilerplate:\n\n\n```typescript\nclass ListNode {\n constructor(\n public val: number = 0,\n public next: ListNode | null = null\n ) {}\n}\n\n// This is equivalent to the longer version above.\n// The 'public' keyword automatically creates and assigns the property.\n```\n\n\n**Interfaces vs Classes:** TypeScript also lets you define types with interfaces. For DSA, classes are more common because LeetCode provides them, but interfaces are useful for typing function parameters:\n\n\n```typescript\n// Interface for generic tree operations\ninterface BinaryTree {\n val: number;\n left: BinaryTree | null;\n right: BinaryTree | null;\n}\n\n// Works with any class that has these properties\nfunction height(node: BinaryTree | null): number {\n if (!node) return 0;\n return 1 + Math.max(height(node.left), height(node.right));\n}\n```\n\n\nBuilding linked lists concisely with constructor chaining:\n\n\n```typescript\n// Build list: 1 -> 2 -> 3 -> null\nconst head = new ListNode(1, new ListNode(2, new ListNode(3)));\n```\n","pageType":"dsa"}

Get Premium