/** * Singly Linked List Node * Each node holds a value and a pointer to the next node. * Memory: O(n) — n nodes, each O(1) space */ class ListNode<T> { constructor( public val: T, public next: ListNode<T> | null = null ) {} } /** * Singly Linked List * - prepend O(1) — add to head * - append O(n) — add to tail (O(1) with tail pointer) * - delete O(n) — must find predecessor * - search O(n) — sequential scan */ class LinkedList<T> { private head: ListNode<T> | null = null; private tail: ListNode<T> | null = null; private _size = 0; get size() { return this._size; } /** Add to tail — O(1) with tail pointer */ append(val: T): void { const node = new ListNode(val); if (!this.tail) { this.head = this.tail = node; } else { this.tail.next = node; this.tail = node; } this._size++; } /** Add to head — O(1) */ prepend(val: T): void { const node = new ListNode(val, this.head); this.head = node; if (!this.tail) this.tail = node; this._size++; } /** Remove first occurrence of value — O(n) */ delete(val: T): boolean { if (!this.head) return false; // Special case: removing head if (this.head.val === val) { this.head = this.head.next; if (!this.head) this.tail = null; this._size--; return true; } // Find predecessor of target node let curr = this.head; while (curr.next) { if (curr.next.val === val) { if (curr.next === this.tail) this.tail = curr; curr.next = curr.next.next; this._size--; return true; } curr = curr.next; } return false; } /** Reverse the list in-place — O(n) time, O(1) space */ reverse(): void { let prev: ListNode<T> | null = null; let curr = this.head; this.tail = this.head; // old head becomes new tail while (curr) { const next = curr.next; curr.next = prev; // flip pointer prev = curr; curr = next; } this.head = prev; // prev is now the last seen node = new head } /** Detect cycle using Floyd's two-pointer — O(n) time, O(1) space */ hasCycle(): boolean { let slow = this.head, fast = this.head; while (fast?.next) { slow = slow!.next; // moves 1 step fast = fast.next.next; // moves 2 steps if (slow === fast) return true; // they meet → cycle } return false; } /** Get middle node (slow/fast pointer) — O(n) */ middle(): ListNode<T> | null { let slow = this.head, fast = this.head; while (fast?.next) { slow = slow!.next; fast = fast.next.next; } return slow; // when fast reaches end, slow is at middle } toArray(): T[] { const res: T[] = []; let curr = this.head; while (curr) { res.push(curr.val); curr = curr.next; } return res; } }

/** * Stack — Last In First Out * Uses an array internally. All operations O(1) amortized. * Use cases: undo/redo, DFS, expression parsing, call stack */ class Stack<T> { private data: T[] = []; push(val: T): void { this.data.push(val); } pop(): T | undefined { return this.data.pop(); } peek(): T | undefined { return this.data[this.data.length - 1]; } isEmpty(): boolean { return this.data.length === 0; } get size(): number { return this.data.length; } } /** * Queue — First In First Out (using two stacks — O(1) amortized) * Naive array approach: enqueue O(1), dequeue O(n) [shift is O(n)] * Two-stack approach: both operations O(1) amortized */ class Queue<T> { private inbox: T[] = []; // push into this private outbox: T[] = []; // pop from this enqueue(val: T): void { this.inbox.push(val); } dequeue(): T | undefined { if (this.outbox.length === 0) { // Transfer all from inbox to outbox — reverses order (FIFO preserved) while (this.inbox.length) this.outbox.push(this.inbox.pop()!); } return this.outbox.pop(); } peek(): T | undefined { if (!this.outbox.length) while (this.inbox.length) this.outbox.push(this.inbox.pop()!); return this.outbox[this.outbox.length - 1]; } get size(): number { return this.inbox.length + this.outbox.length; } isEmpty(): boolean { return this.size === 0; } } /** * Monotonic Stack — maintains increasing or decreasing order * Use case: Next Greater Element, Largest Rectangle in Histogram */ function nextGreaterElement(nums: number[]): number[] { const result = new Array(nums.length).fill(-1); const stack: number[] = []; // stores INDICES of elements waiting for answer for (let i = 0; i < nums.length; i++) { // Pop all elements smaller than current — current is their "next greater" while (stack.length && nums[stack[stack.length - 1]] < nums[i]) { result[stack.pop()!] = nums[i]; } stack.push(i); // push index of current element } return result; // remaining in stack have no greater element → stay -1 }

class TreeNode<T> { constructor( public val: T, public left: TreeNode<T> | null = null, public right: TreeNode<T> | null = null ) {} } // ─── DFS Traversals ─────────────────────────────────────── // Pre-order: Root → Left → Right (serialize tree, copy tree) function preOrder<T>(root: TreeNode<T> | null): T[] { if (!root) return []; return [root.val, ...preOrder(root.left), ...preOrder(root.right)]; } // In-order: Left → Root → Right (BST sorted order!) function inOrder<T>(root: TreeNode<T> | null): T[] { if (!root) return []; return [...inOrder(root.left), root.val, ...inOrder(root.right)]; } // Post-order: Left → Right → Root (delete tree, evaluate expression) function postOrder<T>(root: TreeNode<T> | null): T[] { if (!root) return []; return [...postOrder(root.left), ...postOrder(root.right), root.val]; } // Iterative in-order (avoids stack overflow for deep trees) function inOrderIterative<T>(root: TreeNode<T> | null): T[] { const result: T[] = [], stack: TreeNode<T>[] = []; let curr = root; while (curr || stack.length) { while (curr) { stack.push(curr); curr = curr.left; } // go left curr = stack.pop()!; result.push(curr.val); // visit curr = curr.right; // go right } return result; } // ─── BFS / Level-order ───────────────────────────────────── function levelOrder<T>(root: TreeNode<T> | null): T[][] { if (!root) return []; const result: T[][] = [], queue: TreeNode<T>[] = [root]; while (queue.length) { const level: T[] = []; const size = queue.length; // snapshot size — process ONE level for (let i = 0; i < size; i++) { const node = queue.shift()!; level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(level); } return result; } // ─── Height of tree — O(n) ──────────────────────────────── function height<T>(root: TreeNode<T> | null): number { if (!root) return 0; return 1 + Math.max(height(root.left), height(root.right)); } // ─── Diameter (longest path between any two nodes) ───────── function diameter<T>(root: TreeNode<T> | null): number { let maxDia = 0; function dfs(node: TreeNode<T> | null): number { if (!node) return 0; const L = dfs(node.left), R = dfs(node.right); maxDia = Math.max(maxDia, L + R); // path through this node return 1 + Math.max(L, R); // height contribution upward } dfs(root); return maxDia; } // ─── Lowest Common Ancestor — O(n) ──────────────────────── function lca<T>( root: TreeNode<T> | null, p: T, q: T ): TreeNode<T> | null { if (!root || root.val === p || root.val === q) return root; const left = lca(root.left, p, q); const right = lca(root.right, p, q); // If both sides return non-null → root is LCA if (left && right) return root; return left ?? right; // one side found both nodes }

/** * BST Property: left.val < node.val < right.val for ALL nodes * Average case: O(log n) for insert/search/delete * Worst case: O(n) when tree is skewed (like a linked list) * Use self-balancing (AVL, Red-Black) to guarantee O(log n) */ class BST { root: TreeNode<number> | null = null; /** Insert — avg O(log n), worst O(n) */ insert(val: number): void { const insertNode = (node: TreeNode<number> | null): TreeNode<number> => { if (!node) return new TreeNode(val); if (val < node.val) node.left = insertNode(node.left); else if (val > node.val) node.right = insertNode(node.right); // Equal: duplicates ignored (or add count field) return node; }; this.root = insertNode(this.root); } /** Search — avg O(log n) */ search(val: number): boolean { let curr = this.root; while (curr) { if (val === curr.val) return true; curr = val < curr.val ? curr.left : curr.right; } return false; } /** Delete — avg O(log n). 3 cases: * 1. Leaf: simply remove * 2. One child: replace node with child * 3. Two children: replace with in-order successor (min of right subtree) */ delete(val: number): void { const del = (node: TreeNode<number> | null): TreeNode<number> | null => { if (!node) return null; if (val < node.val) { node.left = del(node.left); return node; } if (val > node.val) { node.right = del(node.right); return node; } // Found the node to delete: if (!node.left) return node.right; // case 1 or 2 if (!node.right) return node.left; // case 2 // Case 3: find in-order successor (min of right subtree) let successor = node.right; while (successor.left) successor = successor.left; node.val = successor.val; // copy successor value node.right = del(node.right); // delete successor return node; }; this.root = del(this.root); } /** Validate BST — pass valid range down — O(n) */ isValid(): boolean { const check = ( node: TreeNode<number> | null, min = -Infinity, max = Infinity ): boolean => { if (!node) return true; if (node.val <= min || node.val >= max) return false; return check(node.left, min, node.val) && check(node.right, node.val, max); }; return check(this.root); } /** kth Smallest via in-order (BST sorted) — O(k) */ kthSmallest(k: number): number | null { let count = 0, result: number | null = null; const inOrder = (node: TreeNode<number> | null): void => { if (!node || result !== null) return; inOrder(node.left); if (++count === k) { result = node.val; return; } inOrder(node.right); }; inOrder(this.root); return result; } }

/** * Binary Min-Heap stored in array. * Parent of i = Math.floor((i-1)/2) * Left child = 2*i + 1 * Right child = 2*i + 2 * * insert O(log n) — add to end, bubble up * extractMin O(log n) — swap root with last, remove, bubble down * peek O(1) * buildHeap O(n) — heapify from bottom */ class MinHeap { private heap: number[] = []; get size() { return this.heap.length; } peek(): number | undefined { return this.heap[0]; } /** Add element and restore heap property upward */ insert(val: number): void { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } /** Remove and return minimum element — O(log n) */ extractMin(): number | undefined { if (!this.heap.length) return undefined; const min = this.heap[0]; const last = this.heap.pop()!; if (this.heap.length) { this.heap[0] = last; // move last to root this.bubbleDown(0); // restore heap property } return min; } private bubbleUp(i: number): void { while (i > 0) { const parent = Math.floor((i - 1) / 2); if (this.heap[parent] <= this.heap[i]) break; [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]]; i = parent; } } private bubbleDown(i: number): void { const n = this.heap.length; while (true) { let smallest = i; const L = 2 * i + 1, R = 2 * i + 2; if (L < n && this.heap[L] < this.heap[smallest]) smallest = L; if (R < n && this.heap[R] < this.heap[smallest]) smallest = R; if (smallest === i) break; [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]]; i = smallest; } } /** Build heap from array in O(n) using sift-down from bottom-up */ buildHeap(arr: number[]): void { this.heap = [...arr]; // Start from last internal node and sift down each for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) { this.bubbleDown(i); } } } // ─── K Largest Elements using MinHeap ───────────────────── function kLargest(nums: number[], k: number): number[] { const heap = new MinHeap(); for (const n of nums) { heap.insert(n); if (heap.size > k) heap.extractMin(); // keep only k largest } const result: number[] = []; while (heap.size) result.unshift(heap.extractMin()!); return result; }

/** * Trie (Prefix Tree) * - Each node has up to 26 children (for lowercase English) * - insert O(m) where m = word length * - search O(m) * - startsWith O(m) * - Space: O(n * m) in worst case (n words, m avg length) * * Use cases: autocomplete, spell check, IP routing, word search grid */ class TrieNode { children: Map<string, TrieNode> = new Map(); isEnd = false; count = 0; // how many words pass through this node } class Trie { private root = new TrieNode(); /** Insert word — O(m) */ insert(word: string): void { let node = this.root; for (const ch of word) { if (!node.children.has(ch)) node.children.set(ch, new TrieNode()); node = node.children.get(ch)!; node.count++; } node.isEnd = true; } /** Exact match search — O(m) */ search(word: string): boolean { const node = this.traverse(word); return !!node?.isEnd; } /** Prefix check — O(m) */ startsWith(prefix: string): boolean { return this.traverse(prefix) !== null; } private traverse(str: string): TrieNode | null { let node: TrieNode | undefined = this.root; for (const ch of str) { node = node.children.get(ch); if (!node) return null; } return node; } /** Autocomplete: get all words with given prefix — O(m + k) */ autocomplete(prefix: string): string[] { const node = this.traverse(prefix); if (!node) return []; const results: string[] = []; const dfs = (curr: TrieNode, path: string): void => { if (curr.isEnd) results.push(prefix + path); for (const [ch, child] of curr.children) dfs(child, path + ch); }; dfs(node, ""); return results; } }

/** * Graph Representations: * Adjacency List — O(V+E) space, O(1) add edge, O(degree) neighbors * Adjacency Matrix — O(V²) space, O(1) edge check, good for dense graphs */ class Graph { private adj: Map<number, { node: number; weight: number }[]> = new Map(); addEdge(u: number, v: number, weight = 1, directed = false): void { if (!this.adj.has(u)) this.adj.set(u, []); if (!this.adj.has(v)) this.adj.set(v, []); this.adj.get(u)!.push({ node: v, weight }); if (!directed) this.adj.get(v)!.push({ node: u, weight }); } /** * BFS — O(V+E) * Uses a queue. Explores level by level. * Best for: shortest path in UNWEIGHTED graph, level-order, nearest neighbors */ bfs(start: number): number[] { const visited = new Set<number>([start]); const queue = [start], order: number[] = []; while (queue.length) { const node = queue.shift()!; order.push(node); for (const { node: nb } of this.adj.get(node) ?? []) { if (!visited.has(nb)) { visited.add(nb); queue.push(nb); } } } return order; } /** * DFS — O(V+E) * Explores as deep as possible before backtracking. * Best for: cycle detection, topological sort, connected components, maze */ dfs(start: number): number[] { const visited = new Set<number>(); const order: number[] = []; const explore = (node: number): void => { visited.add(node); order.push(node); for (const { node: nb } of this.adj.get(node) ?? []) { if (!visited.has(nb)) explore(nb); } }; explore(start); return order; } /** * Dijkstra — O((V+E) log V) with min-heap * Shortest path in WEIGHTED graph (non-negative weights only). * Negative weights → use Bellman-Ford instead. */ dijkstra(start: number): Map<number, number> { const dist = new Map<number, number>(); for (const node of this.adj.keys()) dist.set(node, Infinity); dist.set(start, 0); // Min-heap: [distance, node] — use sorted array for simplicity // In production use a proper priority queue for O(log n) extract-min const pq: [number, number][] = [[0, start]]; while (pq.length) { pq.sort((a, b) => a[0] - b[0]); // O(n log n) — replace with heap const [d, u] = pq.shift()!; if (d > dist.get(u)!) continue; // stale entry for (const { node: v, weight: w } of this.adj.get(u) ?? []) { const nd = d + w; if (nd < dist.get(v)!) { dist.set(v, nd); pq.push([nd, v]); } } } return dist; } /** * Topological Sort — Kahn's Algorithm (BFS-based) * O(V+E). Only works on DAG (Directed Acyclic Graph). * Use case: build systems, course prerequisites, task scheduling. */ topologicalSort(nodes: number[]): number[] { const inDegree = new Map<number, number>(); for (const n of nodes) inDegree.set(n, 0); for (const [, edges] of this.adj) { for (const { node: v } of edges) inDegree.set(v, (inDegree.get(v) ?? 0) + 1); } const queue = nodes.filter(n => inDegree.get(n) === 0); const order: number[] = []; while (queue.length) { const u = queue.shift()!; order.push(u); for (const { node: v } of this.adj.get(u) ?? []) { inDegree.set(v, inDegree.get(v)! - 1); if (inDegree.get(v) === 0) queue.push(v); } } return order.length === nodes.length ? order : []; // empty if cycle } }

/** * Union-Find (Disjoint Set Union) * Operations: O(α(n)) ≈ O(1) amortized with path compression + union by rank * α = inverse Ackermann function — effectively constant for all practical n * * Use cases: * - Kruskal's MST algorithm * - Number of connected components * - Detect cycle in undirected graph * - Dynamic connectivity problems */ class UnionFind { private parent: number[]; private rank: number[]; private _components: number; constructor(n: number) { this.parent = Array.from({ length: n }, (_, i) => i); // each is own parent this.rank = new Array(n).fill(0); this._components = n; } /** Find root with PATH COMPRESSION — O(α(n)) */ find(x: number): number { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); // flatten path to root } return this.parent[x]; } /** Union two sets by RANK — O(α(n)) */ union(x: number, y: number): boolean { const rx = this.find(x), ry = this.find(y); if (rx === ry) return false; // already connected — would form cycle! // Attach smaller tree under larger tree to keep depth minimal if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry; else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx; else { this.parent[ry] = rx; this.rank[rx]++; } this._components--; return true; } connected(x: number, y: number): boolean { return this.find(x) === this.find(y); } get components(): number { return this._components; } } // Number of islands using Union-Find function numIslands(grid: string[][]): number { const R = grid.length, C = grid[0].length; const uf = new UnionFind(R * C); let water = 0; for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) { if (grid[r][c] === '0') { water++; continue; } for (const [dr, dc] of [[1,0],[0,1]]) { // check down & right only const nr = r+dr, nc = c+dc; if (nr < R && nc < C && grid[nr][nc] === '1') uf.union(r*C+c, nr*C+nc); } } return uf.components - water; }

/** * Quick Sort — avg O(n log n), worst O(n²), space O(log n) (call stack) * In-place. Not stable. Best for large arrays in practice. * Partition: choose pivot, rearrange so left < pivot < right, recurse. */ function quickSort(arr: number[], lo = 0, hi = arr.length - 1): number[] { if (lo < hi) { const p = partition(arr, lo, hi); quickSort(arr, lo, p - 1); quickSort(arr, p + 1, hi); } return arr; } function partition(arr: number[], lo: number, hi: number): number { const pivot = arr[hi]; let i = lo - 1; for (let j = lo; j < hi; j++) { if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]; return i + 1; } /** * Merge Sort — O(n log n) always, space O(n), stable * Divide array in half, sort each half, merge. * Preferred when stability matters or for linked lists. */ function mergeSort(arr: number[]): number[] { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid))); } function merge(L: number[], R: number[]): number[] { const res: number[] = []; let i = 0, j = 0; while (i < L.length && j < R.length) { res.push(L[i] <= R[j] ? L[i++] : R[j++]); } return [...res, ...L.slice(i), ...R.slice(j)]; } /** * Counting Sort — O(n + k) where k = value range * Only for integers in known range. Not comparison-based. */ function countingSort(arr: number[], max: number): number[] { const count = new Array(max + 1).fill(0); for (const n of arr) count[n]++; const result: number[] = []; count.forEach((c, v) => result.push(...new Array(c).fill(v))); return result; }

/** * Binary Search — O(log n) * TEMPLATE: Always use [lo, hi] inclusive. * Condition check determines which half to go to. */ // Exact search function binarySearch(arr: number[], target: number): number { let lo = 0, hi = arr.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); // avoids overflow vs (lo+hi)/2 if (arr[mid] === target) return mid; else if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } // Left boundary (first occurrence / leftmost valid position) function lowerBound(arr: number[], target: number): number { let lo = 0, hi = arr.length; // hi = length (exclusive) while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (arr[mid] < target) lo = mid + 1; else hi = mid; // keep going left } return lo; // insertion point = first index where arr[i] >= target } // Search in rotated sorted array — O(log n) function searchRotated(arr: number[], target: number): number { let lo = 0, hi = arr.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (arr[mid] === target) return mid; // Determine which half is sorted if (arr[lo] <= arr[mid]) { // left half is sorted if (arr[lo] <= target && target < arr[mid]) hi = mid - 1; else lo = mid + 1; } else { // right half is sorted if (arr[mid] < target && target <= arr[hi]) lo = mid + 1; else hi = mid - 1; } } return -1; } // Binary search on answer (minimize/maximize a value) function minEatingSpeed(piles: number[], h: number): number { let lo = 1, hi = Math.max(...piles); while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); const hoursNeeded = piles.reduce((s, p) => s + Math.ceil(p / mid), 0); if (hoursNeeded <= h) hi = mid; // mid might work, try smaller else lo = mid + 1; // too slow } return lo; }

/** * DP Framework: * 1. Define subproblem (what does dp[i] mean?) * 2. Identify recurrence relation * 3. Base case * 4. Iteration order (ensure subproblems are solved before needed) */ // ─── Fibonacci (memoization vs tabulation) ───────────────── function fib(n: number, memo = new Map<number,number>()): number { if (n <= 1) return n; if (memo.has(n)) return memo.get(n)!; const res = fib(n - 1, memo) + fib(n - 2, memo); memo.set(n, res); return res; } // ─── Coin Change (min coins) ────────────────────────────── // dp[i] = min coins to make amount i function coinChange(coins: number[], amount: number): number { const dp = new Array(amount + 1).fill(Infinity); dp[0] = 0; // base: 0 coins to make 0 for (let i = 1; i <= amount; i++) { for (const coin of coins) { if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } return dp[amount] === Infinity ? -1 : dp[amount]; } // ─── Longest Common Subsequence ──────────────────────────── // dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1] function lcs(s1: string, s2: string): number { const m = s1.length, n = s2.length; const dp = Array.from({ length: m+1 }, () => new Array(n+1).fill(0)); for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { dp[i][j] = s1[i-1] === s2[j-1] ? dp[i-1][j-1] + 1 // chars match — extend LCS : Math.max(dp[i-1][j], dp[i][j-1]); // skip one char } } return dp[m][n]; } // ─── Longest Increasing Subsequence — O(n log n) ────────── function lis(nums: number[]): number { const tails: number[] = []; // tails[i] = smallest tail of all IS of length i+1 for (const n of nums) { let lo = 0, hi = tails.length; while (lo < hi) { // binary search for insertion position const mid = (lo + hi) >> 1; tails[mid] < n ? lo = mid + 1 : hi = mid; } tails[lo] = n; // extend or replace tail } return tails.length; } // ─── 0/1 Knapsack ───────────────────────────────────────── // dp[i][w] = max value using first i items with capacity w function knapsack(weights: number[], values: number[], W: number): number { const n = weights.length; const dp = new Array(W + 1).fill(0); // space-optimized 1D for (let i = 0; i < n; i++) { for (let w = W; w >= weights[i]; w--) { // reverse to avoid reuse dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]); } } return dp[W]; }

// ─── Fixed-size sliding window (max sum of k elements) ───── function maxSumK(arr: number[], k: number): number { let sum = arr.slice(0, k).reduce((a, b) => a + b, 0); let max = sum; for (let i = k; i < arr.length; i++) { sum += arr[i] - arr[i - k]; // slide: add new, remove old max = Math.max(max, sum); } return max; } // ─── Variable-size window (longest substring without repeat) function lengthOfLongestSubstring(s: string): number { const last = new Map<string, number>(); let left = 0, max = 0; for (let right = 0; right < s.length; right++) { const ch = s[right]; // Shrink window if char was seen inside current window if (last.has(ch) && last.get(ch)! >= left) left = last.get(ch)! + 1; last.set(ch, right); max = Math.max(max, right - left + 1); } return max; } // ─── Two Pointers: Container with Most Water ─────────────── function maxWater(height: number[]): number { let lo = 0, hi = height.length - 1, max = 0; while (lo < hi) { max = Math.max(max, Math.min(height[lo], height[hi]) * (hi - lo)); // Move the shorter side inward — moving taller can't improve area height[lo] < height[hi] ? lo++ : hi--; } return max; } // ─── Two Pointers: 3Sum ─────────────────────────────────── function threeSum(nums: number[]): number[][] { nums.sort((a, b) => a - b); const result: number[][] = []; for (let i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] === nums[i-1]) continue; // skip duplicates let lo = i + 1, hi = nums.length - 1; while (lo < hi) { const sum = nums[i] + nums[lo] + nums[hi]; if (sum === 0) { result.push([nums[i], nums[lo], nums[hi]]); lo++; hi--; } else if (sum < 0) lo++; else hi--; while (lo < hi && nums[lo] === nums[lo-1]) lo++; // skip dups while (lo < hi && nums[hi] === nums[hi+1]) hi--; } } return result; }