// two pointers - in-place array modification const modifyarray = (arr) => { let writepointer = 0; for (let readpointer = 0; readpointer < arr.length; readpointer++) { if (/* condition */) { [arr[writepointer], arr[readpointer]] = [arr[readpointer], arr[writepointer]]; writepointer++; } } return writepointer; // often returns new length or modified position }; // fast and slow pointers (floyd's cycle detection) const hascycle = (head) => { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) return true; } return false; }; // sliding window - fixed size const fixedslidingwindow = (arr, k) => { let sum = 0; // initialize first window for (let i = 0; i < k; i++) { sum += arr[i]; } let maxsum = sum; // slide window for (let i = k; i < arr.length; i++) { sum = sum - arr[i - k] + arr[i]; maxsum = math.max(maxsum, sum); } return maxsum; }; // sliding window - variable size const varslidingwindow = (arr, target) => { let start = 0, sum = 0, minlen = infinity; for (let end = 0; end < arr.length; end++) { sum += arr[end]; while (sum >= target) { minlen = math.min(minlen, end - start + 1); sum -= arr[start]; start++; } } return minlen === infinity ? 0 : minlen; }; // bfs - level order traversal const levelorder = (root) => { if (!root) return []; const result = []; const queue = [root]; while (queue.length) { const levelsize = queue.length; const currentlevel = []; for (let i = 0; i < levelsize; i++) { const node = queue.shift(); currentlevel.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(currentlevel); } return result; }; // dfs - recursive template const dfs = (root) => { const result = []; const traverse = (node) => { if (!node) return; // pre-order result.push(node.val); traverse(node.left); // in-order would be here traverse(node.right); // post-order would be here }; traverse(root); return result; }; // backtracking template const backtrack = (nums) => { const result = []; const bt = (path, choices) => { if (/* ending condition */) { result.push([...path]); return; } for (let i = 0; i < choices.length; i++) { // make choice path.push(choices[i]); // recurse bt(path, /* remaining choices */); // undo choice path.pop(); } }; bt([], nums); return result; }; // dynamic programming - bottom up template const dpbottomup = (n) => { const dp = new array(n + 1).fill(0); dp[0] = 1; // base case for (let i = 1; i <= n; i++) { for (let j = 0; j < i; j++) { dp[i] += dp[j] * /* some calculation */; } } return dp[n]; }; // dynamic programming - top down template const dptopdown = (n) => { const memo = new map(); const dp = (n) => { if (n <= 1) return 1; if (memo.has(n)) return memo.get(n); let result = 0; for (let i = 0; i < n; i++) { result += dp(i) * /* some calculation */; } memo.set(n, result); return result; }; return dp(n); }; // monotonic stack template const monotonicstack = (arr) => { const stack = []; // [index, value] const result = new array(arr.length).fill(-1); for (let i = 0; i < arr.length; i++) { while (stack.length && stack[stack.length - 1][1] > arr[i]) { const [previndex, _] = stack.pop(); result[previndex] = i - previndex; } stack.push([i, arr[i]]); } return result; }; // prefix sum const prefixsum = (arr) => { const prefix = [0]; for (let i = 0; i < arr.length; i++) { prefix.push(prefix[prefix.length - 1] + arr[i]); } // sum of range [i, j] = prefix[j + 1] - prefix[i] return prefix; }; // binary search variations const binarysearchleftmost = (arr, target) => { let left = 0, right = arr.length; while (left < right) { const mid = math.floor((left + right) / 2); if (arr[mid] < target) left = mid + 1; else right = mid; } return left; }; const binarysearchrightmost = (arr, target) => { let left = 0, right = arr.length; while (left < right) { const mid = math.floor((left + right) / 2); if (arr[mid] <= target) left = mid + 1; else right = mid; } return left - 1; }; // trie operations class trienode { constructor() { this.children = new map(); this.isendofword = false; } } class trie { constructor() { this.root = new trienode(); } insert(word) { let node = this.root; for (const char of word) { if (!node.children.has(char)) { node.children.set(char, new trienode()); } node = node.children.get(char); } node.isendofword = true; } search(word) { let node = this.root; for (const char of word) { if (!node.children.has(char)) return false; node = node.children.get(char); } return node.isendofword; } startswith(prefix) { let node = this.root; for (const char of prefix) { if (!node.children.has(char)) return false; node = node.children.get(char); } return true; } } // union find (disjoint set) class unionfind { constructor(n) { this.parent = array.from({length: n}, (_, i) => i); this.rank = new array(n).fill(0); } find(x) { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); // path compression } return this.parent[x]; } union(x, y) { let rootx = this.find(x); let rooty = this.find(y); if (rootx !== rooty) { if (this.rank[rootx] < this.rank[rooty]) { [rootx, rooty] = [rooty, rootx]; } this.parent[rooty] = rootx; if (this.rank[rootx] === this.rank[rooty]) { this.rank[rootx]++; } } } }
// O(1) - Constant Array.push(), Array.pop(), Map.set(), Map.get() // O(log n) - Logarithmic Binary Search, Balanced BST operations // O(n) - Linear Array traversal, Linear Search // O(n log n) - Linearithmic Efficient sorting (Array.sort()) // O(n²) - Quadratic Nested loops, Simple sorting algorithms // O(2ⁿ) - Exponential Recursive solutions without memoization
