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