# Example: Binary Search
def binary_search(arr, x):
    l, r = 0, len(arr)-1
    while l <= r:
        m = (l + r) // 2
        if arr[m] == x: return m
        elif arr[m] < x: l = m + 1
        else: r = m - 1
    return -1
# T(n) = O(log n)

// C++: Merge Intervals
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;
    for (auto& i : intervals) {
        if (res.empty() || res.back()[1] < i[0])
            res.push_back(i);
        else
            res.back()[1] = max(res.back()[1], i[1]);
    }
    return res;
}

# Detect Cycle (Floyd’s Tortoise-Hare)
def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast: return True
    return False

// Monotonic Stack: Next Greater Element
vector<int> nextGreater(vector<int>& arr) {
    int n = arr.size();
    vector<int> res(n, -1);
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && arr[s.top()] < arr[i]) {
            res[s.top()] = arr[i];
            s.pop();
        }
        s.push(i);
    }
    return res;
}

# Iterative Inorder
def inorder(root):
    stack, res = [], []
    curr = root
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        res.append(curr.val)
        curr = curr.right
    return res

# Kth Largest Element
import heapq
def findKthLargest(nums, k):
    return heapq.nlargest(k, nums)[-1]

// LRU Cache (C++)
class LRUCache {
    int cap;
    list<pair<int,int>> dll;  // {key, val}
    unordered_map<int, list<pair<int,int>>::iterator> mp;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (mp.find(key) == mp.end()) return -1;
        dll.splice(dll.begin(), dll, mp[key]);
        mp[key] = dll.begin();
        return dll.begin()->second;
    }
    void put(int key, int value) {
        if (get(key) != -1) {
            dll.begin()->second = value;
            return;
        }
        if (dll.size() == cap) {
            int del = dll.back().first;
            dll.pop_back();
            mp.erase(del);
        }
        dll.push_front({key, value});
        mp[key] = dll.begin();
    }
};

# Dijkstra (Python)
import heapq
def dijkstra(graph, start):
    pq = [(0, start)]
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# 0/1 Knapsack
def knapsack(W, wt, val):
    n = len(val)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

// Union-Find
vector<int> parent, rank;
void make_set(int v) {
    parent[v] = v; rank[v] = 0;
}
int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
    a = find_set(a); b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b]) swap(a,b);
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a]++;
    }
}

Arrays      : Two-pointer, Sliding Window, Prefix Sum
LL          : Fast-Slow, Reverse, Dummy Node
Stack       : Monotonic, Parentheses
Tree        : Inorder=Sorted, LCA=Paths, Diameter=Height
Heap        : Kth, Merge K, Median Stream
Hash        : Two Sum, LRU, Subarray Sum
Graph       : BFS=SP, DFS=Topo, Dijkstra=PriorityQ
DP          : 0/1 vs Unbounded, LCS, Grid
Greedy      : Activity, Huffman, Fractional
Advanced    : Trie, Segment Tree, BIT, DSU