// 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 (floyds 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

登录后复制