Algorithm Cheat Sheets

📐 Complexity Analysis Varies / Varies

// Analyze nested loops
int total = 0;
for (int i = 0; i < n; i++) {        // O(n)
    for (int j = i; j < n; j++) {     // O(n - i)
        total++;                       // O(1)
    }
}
// Total: sum(n-i) for i=0..n-1 = O(n^2)
// Drop constants and lower-order terms

// Analyze nested loops
total := 0
for i := 0; i < n; i++ {        // O(n)
    for j := i; j < n; j++ {     // O(n - i)
        total++                   // O(1)
    }
}
// Total: sum(n-i) for i=0..n-1 = O(n^2)
// Drop constants and lower-order terms

# Analyze nested loops
total = 0
for i in range(n):        # O(n)
    for j in range(i, n): # O(n - i)
        total += 1         # O(1)
# Total: sum(n-i) for i=0..n-1 = O(n^2)
# Drop constants and lower-order terms

// Analyze nested loops
let mut total = 0;
for i in 0..n {                // O(n)
    for _j in i..n {           // O(n - i)
        total += 1;            // O(1)
    }
}
// Total: sum(n-i) for i=0..n-1 = O(n^2)
// Drop constants and lower-order terms

// Analyze nested loops
let total = 0;
for (let i = 0; i < n; i++) {        // O(n)
    for (let j = i; j < n; j++) {     // O(n - i)
        total++;                       // O(1)
    }
}
// Total: sum(n-i) for i=0..n-1 = O(n^2)
// Drop constants and lower-order terms

Use when

Analyzing algorithm performance
Comparing approaches
Interview complexity questions
Nested loop analysis

Watch out

Confusing average and worst case
Forgetting hidden costs (e.g., string concatenation is O(n))
Not accounting for space used by recursion stack

👉 Two Pointers O(n) / O(1)

int[] twoPointers(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int curr = arr[left] + arr[right];
        if (curr == target) return new int[]{left, right};
        else if (curr < target) left++;
        else right--;
    }
    return new int[]{};
}

func twoPointers(arr []int, target int) []int {
    left, right := 0, len(arr)-1
    for left < right {
        curr := arr[left] + arr[right]
        if curr == target {
            return []int{left, right}
        } else if curr < target {
            left++
        } else {
            right--
        }
    }
    return nil
}

def two_pointers(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        curr = arr[left] + arr[right]
        if curr == target:
            return [left, right]
        elif curr < target:
            left += 1
        else:
            right -= 1
    return []

fn two_pointers(arr: &[i32], target: i32) -> Vec<usize> {
    let (mut left, mut right) = (0, arr.len() - 1);
    while left < right {
        let curr = arr[left] + arr[right];
        if curr == target { return vec![left, right]; }
        else if curr < target { left += 1; }
        else { right -= 1; }
    }
    vec![]
}

function twoPointers(arr: number[], target: number): number[] {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        const curr = arr[left] + arr[right];
        if (curr === target) return [left, right];
        else if (curr < target) left++;
        else right--;
    }
    return [];
}

Use when

Sorted array or linked list
Find a pair that satisfies a condition
Compare elements from both ends
In-place operation without extra space

Watch out

Forgetting to handle duplicates
Off-by-one with < vs <=
Assuming input is sorted

🪟 Sliding Window O(n) / O(k)

int slidingWindow(String s, int k) {
    Map<Character, Integer> counts = new HashMap<>();
    int left = 0, result = 0;
    for (int right = 0; right < s.length(); right++) {
        counts.merge(s.charAt(right), 1, Integer::sum);
        while (counts.size() > k) {
            char c = s.charAt(left);
            counts.merge(c, -1, Integer::sum);
            if (counts.get(c) == 0) counts.remove(c);
            left++;
        }
        result = Math.max(result, right - left + 1);
    }
    return result;
}

func slidingWindow(s string, k int) int {
    counts := map[byte]int{}
    left, result := 0, 0
    for right := 0; right < len(s); right++ {
        counts[s[right]]++
        for len(counts) > k {
            counts[s[left]]--
            if counts[s[left]] == 0 {
                delete(counts, s[left])
            }
            left++
        }
        if right-left+1 > result {
            result = right - left + 1
        }
    }
    return result
}

def sliding_window(s, k):
    counts = {}
    left = 0
    result = 0
    for right in range(len(s)):
        counts[s[right]] = counts.get(s[right], 0) + 1
        while len(counts) > k:  # shrink condition
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        result = max(result, right - left + 1)
    return result

fn sliding_window(s: &[u8], k: usize) -> usize {
    let mut counts = std::collections::HashMap::new();
    let (mut left, mut result) = (0, 0);
    for right in 0..s.len() {
        *counts.entry(s[right]).or_insert(0) += 1;
        while counts.len() > k {
            let c = s[left];
            *counts.get_mut(&c).unwrap() -= 1;
            if counts[&c] == 0 { counts.remove(&c); }
            left += 1;
        }
        result = result.max(right - left + 1);
    }
    result
}

function slidingWindow(s: string, k: number): number {
    const counts = new Map<string, number>();
    let left = 0, result = 0;
    for (let right = 0; right < s.length; right++) {
        counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);
        while (counts.size > k) {
            const c = s[left];
            counts.set(c, counts.get(c)! - 1);
            if (counts.get(c) === 0) counts.delete(c);
            left++;
        }
        result = Math.max(result, right - left + 1);
    }
    return result;
}

Use when

Contiguous subarray or substring
Longest/shortest with constraint
Fixed or variable window size
'At most K distinct' or 'sum <= target'

Watch out

Shrinking too aggressively (while not if)
Not cleaning up map when count reaches 0
Confusing fixed-size vs variable-size windows

🔍 Modified Binary Search O(log n) / O(1)

int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

func binarySearch(arr []int, target int) int {
    lo, hi := 0, len(arr)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

fn binary_search(arr: &[i32], target: i32) -> i32 {
    let (mut lo, mut hi) = (0i32, arr.len() as i32 - 1);
    while lo <= hi {
        let mid = lo + (hi - lo) / 2;
        if arr[mid as usize] == target { return mid; }
        else if arr[mid as usize] < target { lo = mid + 1; }
        else { hi = mid - 1; }
    }
    -1
}

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);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Use when

Sorted or rotated sorted array
Find boundary/peak/minimum
Search space halvable each step
'Find first/last position'

Watch out

Integer overflow with (lo+hi)/2
Infinite loop from wrong mid+/-1
Wrong comparison for first vs last occurrence

📊 Dynamic Programming O(n^2) typical / O(n)

int dpSolve(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    }
    return Arrays.stream(dp).max().getAsInt();
}

func dpSolve(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    dp[0] = nums[0]
    for i := 1; i < n; i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
    }
    result := dp[0]
    for _, v := range dp {
        if v > result { result = v }
    }
    return result
}

def dp_solve(nums):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]  # base case
    for i in range(1, n):
        dp[i] = max(dp[i - 1] + nums[i], nums[i])
    return max(dp)

fn dp_solve(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut dp = vec![0; n];
    dp[0] = nums[0];
    for i in 1..n {
        dp[i] = (dp[i - 1] + nums[i]).max(nums[i]);
    }
    *dp.iter().max().unwrap()
}

function dpSolve(nums: number[]): number {
    const n = nums.length;
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    for (let i = 1; i < n; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    }
    return Math.max(...dp);
}

Use when

Overlapping subproblems
Optimal substructure
'Minimum cost' / 'maximum value' / 'number of ways'
Can express answer recursively

Watch out

Not identifying the right state
Missing base cases
Not considering space optimization (rolling array)

🔀 Backtracking O(2^n) or O(n!) / O(n)

void backtrack(List<Integer> path, int[] choices,
               List<List<Integer>> result) {
    if (isSolution(path)) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int choice : choices) {
        if (isValid(choice)) {
            path.add(choice);
            backtrack(path, nextChoices, result);
            path.remove(path.size() - 1); // undo
        }
    }
}

func backtrack(path []int, choices []int, result *[][]int) {
    if isSolution(path) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        *result = append(*result, tmp)
        return
    }
    for _, choice := range choices {
        if isValid(choice) {
            path = append(path, choice)
            backtrack(path, nextChoices, result)
            path = path[:len(path)-1] // undo
        }
    }
}

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])
        return
    for choice in choices:
        if is_valid(choice):
            path.append(choice)
            backtrack(path, next_choices)
            path.pop()  # undo choice

fn backtrack(path: &mut Vec<i32>, choices: &[i32],
             result: &mut Vec<Vec<i32>>) {
    if is_solution(path) {
        result.push(path.clone());
        return;
    }
    for &choice in choices {
        if is_valid(choice) {
            path.push(choice);
            backtrack(path, &next_choices, result);
            path.pop(); // undo
        }
    }
}

function backtrack(path: number[], choices: number[],
                   result: number[][]): void {
    if (isSolution(path)) {
        result.push([...path]);
        return;
    }
    for (const choice of choices) {
        if (isValid(choice)) {
            path.push(choice);
            backtrack(path, nextChoices, result);
            path.pop(); // undo
        }
    }
}

Use when

Generate all valid combinations/permutations
'Find all solutions'
Constraint satisfaction
Decision tree exploration

Watch out

Forgetting to undo the choice (backtrack step)
Not pruning invalid branches early
Generating duplicates without sorting+skipping

🌳 Tree Traversal O(n) / O(h) DFS / O(w) BFS

void dfs(TreeNode node) {
    if (node == null) return;
    // preorder: process here
    dfs(node.left);
    // inorder: process here
    dfs(node.right);
    // postorder: process here
}
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null)  queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

func dfs(node *TreeNode) {
    if node == nil { return }
    // preorder: process here
    dfs(node.Left)
    // inorder: process here
    dfs(node.Right)
    // postorder: process here
}
func bfs(root *TreeNode) {
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil  { queue = append(queue, node.Left) }
        if node.Right != nil { queue = append(queue, node.Right) }
    }
}

def dfs(node):
    if not node:
        return
    # preorder: process here
    dfs(node.left)
    # inorder: process here
    dfs(node.right)
    # postorder: process here

def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

fn dfs(node: Option<&Box<TreeNode>>) {
    let Some(n) = node else { return };
    // preorder: process here
    dfs(n.left.as_ref());
    // inorder: process here
    dfs(n.right.as_ref());
    // postorder: process here
}
fn bfs(root: &TreeNode) {
    let mut queue = VecDeque::from([root]);
    while let Some(node) = queue.pop_front() {
        if let Some(l) = &node.left  { queue.push_back(l); }
        if let Some(r) = &node.right { queue.push_back(r); }
    }
}

function dfs(node: TreeNode | null): void {
    if (!node) return;
    // preorder: process here
    dfs(node.left);
    // inorder: process here
    dfs(node.right);
    // postorder: process here
}
function bfs(root: TreeNode): void {
    const queue: TreeNode[] = [root];
    while (queue.length) {
        const node = queue.shift()!;
        if (node.left)  queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}

Use when

Process all nodes in a tree
Level-order traversal needed
Path from root to leaf
Compare left and right subtrees

Watch out

Not handling null nodes
Confusing pre/in/post-order
Using DFS when BFS is needed (shortest path in tree)

📚 Monotonic Stack O(n) / O(n)

int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

func nextGreater(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := range result { result[i] = -1 }
    stack := []int{}
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[top] = nums[i]
        }
        stack = append(stack, i)
    }
    return result
}

def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    return result

fn next_greater(nums: &[i32]) -> Vec<i32> {
    let n = nums.len();
    let mut result = vec![-1; n];
    let mut stack: Vec<usize> = Vec::new();
    for i in 0..n {
        while let Some(&top) = stack.last() {
            if nums[top] >= nums[i] { break; }
            result[stack.pop().unwrap()] = nums[i];
        }
        stack.push(i);
    }
    result
}

function nextGreater(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];
    for (let i = 0; i < n; i++) {
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            result[stack.pop()!] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

Use when

Next greater/smaller element
Histogram/rectangle problems
Temperature/stock span problems
Removing elements that can't be optimal

Watch out

Wrong monotonic direction (increasing vs decreasing)
Forgetting to process remaining stack elements
Not storing indices (just values) when positions matter

🔄 In-Place Reversal O(n) / O(1)

ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

fn reverse_list(head: Option<Box<ListNode>>)
    -> Option<Box<ListNode>> {
    let (mut prev, mut curr) = (None, head);
    while let Some(mut node) = curr {
        curr = node.next.take();
        node.next = prev;
        prev = Some(node);
    }
    prev
}

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Use when

Reverse a linked list or sublist
Rearrange list nodes
Palindrome linked list check
Group reversal (k-group)

Watch out

Losing reference to next node before rewiring
Not handling head/tail connections for sublists
Off-by-one in k-group counting

🐢 Fast & Slow Pointers O(n) / O(1)

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast { return true }
    }
    return false
}

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

// Index-based approach (Rust ownership prevents pointer cycles)
fn has_cycle(next: &[Option<usize>]) -> bool {
    let (mut slow, mut fast) = (0, 0);
    loop {
        slow = match next[slow] { Some(n) => n, None => return false };
        fast = match next[fast] { Some(n) => n, None => return false };
        fast = match next[fast] { Some(n) => n, None => return false };
        if slow == fast { return true; }
    }
}

function hasCycle(head: ListNode | null): boolean {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

Use when

Detect cycle in linked list
Find middle of linked list
Find start of cycle
Happy number problem

Watch out

Not checking both fast and fast.next for null
Forgetting slow starts at head (not head.next)
Wrong meeting point logic for cycle start

➕ Prefix Sum O(n) build, O(1) query / O(n)

int[] buildPrefix(int[] arr) {
    int[] prefix = new int[arr.length + 1];
    for (int i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}
int rangeSum(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

func buildPrefix(arr []int) []int {
    prefix := make([]int, len(arr)+1)
    for i := 0; i < len(arr); i++ {
        prefix[i+1] = prefix[i] + arr[i]
    }
    return prefix
}
func rangeSum(prefix []int, l, r int) int {
    return prefix[r+1] - prefix[l]
}

def build_prefix(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

fn build_prefix(arr: &[i32]) -> Vec<i32> {
    let mut prefix = vec![0; arr.len() + 1];
    for i in 0..arr.len() {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    prefix
}
fn range_sum(prefix: &[i32], l: usize, r: usize) -> i32 {
    prefix[r + 1] - prefix[l]
}

function buildPrefix(arr: number[]): number[] {
    const prefix = [0];
    for (let i = 0; i < arr.length; i++) {
        prefix.push(prefix[i] + arr[i]);
    }
    return prefix;
}
function rangeSum(prefix: number[], l: number, r: number): number {
    return prefix[r + 1] - prefix[l];
}

Use when

Range sum queries
Subarray sum equals K
Count subarrays with given sum
Difference array for range updates

Watch out

Off-by-one in prefix indexing
Forgetting prefix[0] = 0
Not using hash map for subarray sum problems

🗺 Matrix Traversal O(m * n) / O(m * n)

void bfsGrid(int[][] grid, int sr, int sc) {
    int rows = grid.length, cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    visited[sr][sc] = true;
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{sr, sc});
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] d : dirs) {
            int nr = cell[0]+d[0], nc = cell[1]+d[1];
            if (nr >= 0 && nr < rows && nc >= 0
                && nc < cols && !visited[nr][nc]) {
                visited[nr][nc] = true;
                queue.add(new int[]{nr, nc});
            }
        }
    }
}

func bfsGrid(grid [][]int, sr, sc int) {
    rows, cols := len(grid), len(grid[0])
    visited := map[[2]int]bool{{sr, sc}: true}
    queue := [][2]int{{sr, sc}}
    dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
    for len(queue) > 0 {
        r, c := queue[0][0], queue[0][1]
        queue = queue[1:]
        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr >= 0 && nr < rows && nc >= 0 &&
               nc < cols && !visited[[2]int{nr, nc}] {
                visited[[2]int{nr, nc}] = true
                queue = append(queue, [2]int{nr, nc})
            }
        }
    }
}

def bfs_grid(grid, sr, sc):
    rows, cols = len(grid), len(grid[0])
    visited = set()
    visited.add((sr, sc))
    queue = deque([(sr, sc)])
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    while queue:
        r, c = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc))

fn bfs_grid(grid: &[Vec<i32>], sr: usize, sc: usize) {
    let (rows, cols) = (grid.len(), grid[0].len());
    let mut visited = vec![vec![false; cols]; rows];
    visited[sr][sc] = true;
    let mut queue = VecDeque::from([(sr, sc)]);
    let dirs: [(i32, i32); 4] = [(0,1),(1,0),(0,-1),(-1,0)];
    while let Some((r, c)) = queue.pop_front() {
        for (dr, dc) in &dirs {
            let (nr, nc) = (r as i32 + dr, c as i32 + dc);
            if nr >= 0 && nr < rows as i32
               && nc >= 0 && nc < cols as i32 {
                let (nr, nc) = (nr as usize, nc as usize);
                if !visited[nr][nc] {
                    visited[nr][nc] = true;
                    queue.push_back((nr, nc));
                }
            }
        }
    }
}

function bfsGrid(grid: number[][], sr: number, sc: number): void {
    const [rows, cols] = [grid.length, grid[0].length];
    const visited = new Set<string>();
    visited.add(sr + "," + sc);
    const queue: [number, number][] = [[sr, sc]];
    const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
    while (queue.length) {
        const [r, c] = queue.shift()!;
        for (const [dr, dc] of dirs) {
            const [nr, nc] = [r + dr, c + dc];
            const key = nr + "," + nc;
            if (nr >= 0 && nr < rows && nc >= 0
                && nc < cols && !visited.has(key)) {
                visited.add(key);
                queue.push([nr, nc]);
            }
        }
    }
}

Use when

Count islands/regions
Shortest path in grid
Flood fill
Connected components in 2D

Watch out

Not marking visited before adding to queue (duplicate visits)
Forgetting diagonal directions when needed
Modifying input grid vs using visited set

🕸 DFS & BFS O(V + E) / O(V)

void bfs(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    visited.add(start);
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int nb : graph.getOrDefault(node, List.of())) {
            if (visited.add(nb)) queue.add(nb);
        }
    }
}
void dfs(Map<Integer, List<Integer>> graph,
         int node, Set<Integer> visited) {
    visited.add(node);
    for (int nb : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(nb)) dfs(graph, nb, visited);
    }
}

func bfs(graph map[int][]int, start int) {
    visited := map[int]bool{start: true}
    queue := []int{start}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for _, nb := range graph[node] {
            if !visited[nb] {
                visited[nb] = true
                queue = append(queue, nb)
            }
        }
    }
}
func dfs(graph map[int][]int, node int, visited map[int]bool) {
    visited[node] = true
    for _, nb := range graph[node] {
        if !visited[nb] { dfs(graph, nb, visited) }
    }
}

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

fn bfs(graph: &HashMap<i32, Vec<i32>>, start: i32) {
    let mut visited = HashSet::from([start]);
    let mut queue = VecDeque::from([start]);
    while let Some(node) = queue.pop_front() {
        for &nb in &graph[&node] {
            if visited.insert(nb) {
                queue.push_back(nb);
            }
        }
    }
}
fn dfs(graph: &HashMap<i32, Vec<i32>>,
       node: i32, visited: &mut HashSet<i32>) {
    visited.insert(node);
    for &nb in &graph[&node] {
        if !visited.contains(&nb) { dfs(graph, nb, visited); }
    }
}

function bfs(graph: Map<number, number[]>, start: number): void {
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length) {
        const node = queue.shift()!;
        for (const nb of graph.get(node) ?? []) {
            if (!visited.has(nb)) {
                visited.add(nb);
                queue.push(nb);
            }
        }
    }
}
function dfs(graph: Map<number, number[]>,
             node: number, visited: Set<number>): void {
    visited.add(node);
    for (const nb of graph.get(node) ?? []) {
        if (!visited.has(nb)) dfs(graph, nb, visited);
    }
}

Use when

Find path between nodes
Connected components
Shortest path (unweighted)
Detect cycle in graph

Watch out

Not tracking visited nodes (infinite loop)
Using DFS for shortest path (use BFS)
Not handling disconnected components

📅 Overlapping Intervals O(n log n) / O(n)

int[][] mergeIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0]);
    for (int i = 1; i < intervals.length; i++) {
        int[] last = merged.get(merged.size() - 1);
        if (intervals[i][0] <= last[1]) {
            last[1] = Math.max(last[1], intervals[i][1]);
        } else {
            merged.add(intervals[i]);
        }
    }
    return merged.toArray(new int[0][]);
}

func mergeIntervals(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    merged := [][]int{intervals[0]}
    for _, iv := range intervals[1:] {
        last := merged[len(merged)-1]
        if iv[0] <= last[1] {
            last[1] = max(last[1], iv[1])
        } else {
            merged = append(merged, iv)
        }
    }
    return merged
}

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

fn merge_intervals(intervals: &mut Vec<[i32; 2]>) -> Vec<[i32; 2]> {
    intervals.sort_by_key(|iv| iv[0]);
    let mut merged = vec![intervals[0]];
    for iv in &intervals[1..] {
        let last = merged.last_mut().unwrap();
        if iv[0] <= last[1] {
            last[1] = last[1].max(iv[1]);
        } else {
            merged.push(*iv);
        }
    }
    merged
}

function mergeIntervals(intervals: number[][]): number[][] {
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];
    for (const [start, end] of intervals.slice(1)) {
        const last = merged[merged.length - 1];
        if (start <= last[1]) {
            last[1] = Math.max(last[1], end);
        } else {
            merged.push([start, end]);
        }
    }
    return merged;
}

Use when

Merge overlapping intervals
Insert interval into sorted list
Find gaps between intervals
Meeting rooms / minimum platforms

Watch out

Forgetting to sort first
Wrong merge condition (< vs <=)
Not updating end with max(prev.end, curr.end)

🏆 Top K Elements O(n log k) / O(k)

int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        heap.add(num);
        if (heap.size() > k) heap.poll();
    }
    return heap.stream().mapToInt(i -> i).toArray();
}

// Implement heap.Interface for IntHeap (Len, Less, Swap, Push, Pop)
func topK(nums []int, k int) []int {
    h := &IntHeap{}
    for _, num := range nums {
        heap.Push(h, num)
        if h.Len() > k { heap.Pop(h) }
    }
    return []int(*h)
}

import heapq

def top_k(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return list(heap)

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn top_k(nums: &[i32], k: usize) -> Vec<i32> {
    let mut heap = BinaryHeap::new();
    for &num in nums {
        heap.push(Reverse(num));
        if heap.len() > k { heap.pop(); }
    }
    heap.into_iter().map(|Reverse(x)| x).collect()
}

// O(n log k) with min-heap; O(n log n) with sort
function topK(nums: number[], k: number): number[] {
    nums.sort((a, b) => a - b);
    return nums.slice(-k);
}

Use when

K largest/smallest elements
K most frequent
K closest points
Sort by frequency

Watch out

Using max-heap when min-heap needed (and vice versa)
Not handling ties correctly
Forgetting heapq is min-heap in Python

🔤 Trie O(m) per operation / O(m) per word

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}
class Trie {
    TrieNode root = new TrieNode();
    void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }
    boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
        }
        return node.isEnd;
    }
}

type TrieNode struct {
    children map[byte]*TrieNode
    isEnd    bool
}
type Trie struct { root *TrieNode }

func (t *Trie) Insert(word string) {
    node := t.root
    for i := range word {
        ch := word[i]
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: map[byte]*TrieNode{}}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}
func (t *Trie) Search(word string) bool {
    node := t.root
    for i := range word {
        if node.children[word[i]] == nil { return false }
        node = node.children[word[i]]
    }
    return node.isEnd
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

use std::collections::HashMap;
struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end: bool,
}
struct Trie { root: TrieNode }
impl Trie {
    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_insert(
                TrieNode { children: HashMap::new(), is_end: false });
        }
        node.is_end = true;
    }
    fn search(&self, word: &str) -> bool {
        let mut node = &self.root;
        for ch in word.chars() {
            match node.children.get(&ch) {
                Some(n) => node = n,
                None => return false,
            }
        }
        node.is_end
    }
}

class TrieNode {
    children = new Map<string, TrieNode>();
    isEnd = false;
}
class Trie {
    root = new TrieNode();
    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.isEnd = true;
    }
    search(word: string): boolean {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) return false;
            node = node.children.get(ch)!;
        }
        return node.isEnd;
    }
}

Use when

Prefix-based search
Autocomplete / word dictionary
Word search in grid
Longest common prefix

Watch out

Not marking end of word
Not handling deletion properly
Using trie when hash set suffices (no prefix queries needed)

🔗 Union-Find O(alpha(n)) ~ O(1) amortized / O(n)

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
}

type UnionFind struct { parent, rank []int }

func NewUF(n int) *UnionFind {
    p := make([]int, n)
    for i := range p { p[i] = i }
    return &UnionFind{p, make([]int, n)}
}
func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x { uf.parent[x] = uf.Find(uf.parent[x]) }
    return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) bool {
    px, py := uf.Find(x), uf.Find(y)
    if px == py { return false }
    if uf.rank[px] < uf.rank[py] { px, py = py, px }
    uf.parent[py] = px
    if uf.rank[px] == uf.rank[py] { uf.rank[px]++ }
    return true
}

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

struct UnionFind { parent: Vec<usize>, rank: Vec<usize> }
impl UnionFind {
    fn new(n: usize) -> Self {
        Self { parent: (0..n).collect(), rank: vec![0; n] }
    }
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }
    fn union(&mut self, x: usize, y: usize) -> bool {
        let (mut px, mut py) = (self.find(x), self.find(y));
        if px == py { return false; }
        if self.rank[px] < self.rank[py] {
            std::mem::swap(&mut px, &mut py);
        }
        self.parent[py] = px;
        if self.rank[px] == self.rank[py] { self.rank[px] += 1; }
        true
    }
}

class UnionFind {
    parent: number[];
    rank: number[];
    constructor(n: number) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x: number): number {
        if (this.parent[x] !== x)
            this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x: number, y: number): boolean {
        let [px, py] = [this.find(x), this.find(y)];
        if (px === py) return false;
        if (this.rank[px] < this.rank[py]) [px, py] = [py, px];
        this.parent[py] = px;
        if (this.rank[px] === this.rank[py]) this.rank[px]++;
        return true;
    }
}

Use when

Group/cluster detection
Connected components dynamically
'Are X and Y connected?'
Minimum spanning tree (Kruskal's)

Watch out

Forgetting path compression (degrades to O(n))
Not using union by rank
Not counting components correctly

📋 Topological Sort O(V + E) / O(V + E)

List<Integer> topoSort(int n, int[][] edges) {
    int[] inDeg = new int[n];
    Map<Integer, List<Integer>> g = new HashMap<>();
    for (int[] e : edges) {
        g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
        inDeg[e[1]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) if (inDeg[i] == 0) q.add(i);
    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int node = q.poll();
        order.add(node);
        for (int nb : g.getOrDefault(node, List.of()))
            if (--inDeg[nb] == 0) q.add(nb);
    }
    return order.size() == n ? order : List.of();
}

func topoSort(n int, edges [][]int) []int {
    inDeg := make([]int, n)
    graph := make(map[int][]int)
    for _, e := range edges {
        graph[e[0]] = append(graph[e[0]], e[1])
        inDeg[e[1]]++
    }
    queue := []int{}
    for i := 0; i < n; i++ {
        if inDeg[i] == 0 { queue = append(queue, i) }
    }
    order := []int{}
    for len(queue) > 0 {
        node := queue[0]; queue = queue[1:]
        order = append(order, node)
        for _, nb := range graph[node] {
            inDeg[nb]--
            if inDeg[nb] == 0 { queue = append(queue, nb) }
        }
    }
    if len(order) == n { return order }
    return nil
}

def topo_sort(num_nodes, edges):
    in_degree = [0] * num_nodes
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    queue = deque([i for i in range(num_nodes) if in_degree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == num_nodes else []

fn topo_sort(n: usize, edges: &[(usize, usize)]) -> Vec<usize> {
    let mut in_deg = vec![0usize; n];
    let mut graph = vec![vec![]; n];
    for &(u, v) in edges {
        graph[u].push(v);
        in_deg[v] += 1;
    }
    let mut queue: VecDeque<_> =
        (0..n).filter(|&i| in_deg[i] == 0).collect();
    let mut order = vec![];
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &nb in &graph[node] {
            in_deg[nb] -= 1;
            if in_deg[nb] == 0 { queue.push_back(nb); }
        }
    }
    if order.len() == n { order } else { vec![] }
}

function topoSort(n: number, edges: number[][]): number[] {
    const inDeg = new Array(n).fill(0);
    const graph = new Map<number, number[]>();
    for (const [u, v] of edges) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push(v);
        inDeg[v]++;
    }
    const queue: number[] = [];
    for (let i = 0; i < n; i++)
        if (inDeg[i] === 0) queue.push(i);
    const order: number[] = [];
    while (queue.length) {
        const node = queue.shift()!;
        order.push(node);
        for (const nb of graph.get(node) ?? [])
            if (--inDeg[nb] === 0) queue.push(nb);
    }
    return order.length === n ? order : [];
}

Use when

Task scheduling with prerequisites
Course ordering
Build order / dependency resolution
Detect cycle in directed graph

Watch out

Forgetting to check for cycles (result size < V)
Wrong in-degree initialization
Using DFS topo sort but forgetting reverse at end

🎯 Greedy O(n log n) / O(1)

int greedySchedule(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int count = 0, end = Integer.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= end) {
            count++;
            end = iv[1];
        }
    }
    return count;
}

func greedySchedule(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    count, end := 0, math.MinInt
    for _, iv := range intervals {
        if iv[0] >= end {
            count++
            end = iv[1]
        }
    }
    return count
}

def greedy_schedule(intervals):
    intervals.sort(key=lambda x: x[1])  # sort by end time
    count = 0
    end = float('-inf')
    for start, finish in intervals:
        if start >= end:
            count += 1
            end = finish
    return count

fn greedy_schedule(intervals: &mut Vec<[i32; 2]>) -> i32 {
    intervals.sort_by_key(|iv| iv[1]);
    let (mut count, mut end) = (0, i32::MIN);
    for iv in intervals.iter() {
        if iv[0] >= end {
            count += 1;
            end = iv[1];
        }
    }
    count
}

function greedySchedule(intervals: number[][]): number {
    intervals.sort((a, b) => a[1] - b[1]);
    let count = 0, end = -Infinity;
    for (const [start, finish] of intervals) {
        if (start >= end) {
            count++;
            end = finish;
        }
    }
    return count;
}

Use when

Activity selection / scheduling
Minimum coins / jumps
Locally optimal leads to globally optimal
Proof by exchange argument

Watch out

Assuming greedy works without proof
Wrong sorting criterion
Not handling edge cases (empty input, single element)

⚡ Bit Manipulation O(n) or O(1) / O(1)

int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;
}
// Useful bit tricks:
// n & (n - 1)   -> clear lowest set bit
// n & (-n)      -> isolate lowest set bit
// n >> 1        -> divide by 2
// 1 << k        -> 2^k / check kth bit

func singleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result ^= num
    }
    return result
}
// Useful bit tricks:
// n & (n - 1)   -> clear lowest set bit
// n & (-n)      -> isolate lowest set bit
// n >> 1        -> divide by 2
// 1 << k        -> 2^k / check kth bit

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num  # XOR cancels pairs
    return result

# Useful bit tricks:
# n & (n - 1)   -> clear lowest set bit
# n & (-n)      -> isolate lowest set bit
# n >> 1        -> divide by 2
# 1 << k        -> 2^k / check kth bit

fn single_number(nums: &[i32]) -> i32 {
    nums.iter().fold(0, |acc, &x| acc ^ x)
}
// Useful bit tricks:
// n & (n - 1)   -> clear lowest set bit
// n & (-n)      -> isolate lowest set bit
// n >> 1        -> divide by 2
// 1 << k        -> 2^k / check kth bit

function singleNumber(nums: number[]): number {
    return nums.reduce((acc, num) => acc ^ num, 0);
}
// Useful bit tricks:
// n & (n - 1)   -> clear lowest set bit
// n & (-n)      -> isolate lowest set bit
// n >> 1        -> divide by 2
// 1 << k        -> 2^k / check kth bit

Use when

Find single/unique number
Power of 2 check
Counting bits
Subset enumeration with bitmask

Watch out

Signed vs unsigned integer issues
Operator precedence (& before ==)
Forgetting n & (n-1) clears lowest set bit

📈 Monotonic Queue O(n) / O(k)

int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
            dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
            dq.pollLast();
        dq.addLast(i);
        if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];
    }
    return result;
}

func maxSlidingWindow(nums []int, k int) []int {
    dq := []int{}
    result := []int{}
    for i := 0; i < len(nums); i++ {
        for len(dq) > 0 && dq[0] < i-k+1 { dq = dq[1:] }
        for len(dq) > 0 && nums[dq[len(dq)-1]] < nums[i] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
        if i >= k-1 { result = append(result, nums[dq[0]]) }
    }
    return result
}

def max_sliding_window(nums, k):
    dq = deque()  # stores indices
    result = []
    for i in range(len(nums)):
        while dq and dq[0] < i - k + 1:
            dq.popleft()  # remove expired
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()  # maintain decreasing order
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

fn max_sliding_window(nums: &[i32], k: usize) -> Vec<i32> {
    let mut dq = VecDeque::new();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        while dq.front().map_or(false, |&f| f + k <= i) {
            dq.pop_front();
        }
        while dq.back().map_or(false, |&b| nums[b] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if i >= k - 1 { result.push(nums[*dq.front().unwrap()]); }
    }
    result
}

function maxSlidingWindow(nums: number[], k: number): number[] {
    const dq: number[] = [];
    const result: number[] = [];
    for (let i = 0; i < nums.length; i++) {
        while (dq.length && dq[0] < i - k + 1) dq.shift();
        while (dq.length && nums[dq[dq.length - 1]] < nums[i])
            dq.pop();
        dq.push(i);
        if (i >= k - 1) result.push(nums[dq[0]]);
    }
    return result;
}

Use when

Sliding window maximum/minimum
Fixed window with min/max query
Subarray with bounded difference
Jump game with constraints

Watch out

Not removing expired elements from front
Wrong deque direction (max vs min)
Storing values instead of indices

⚖ Two Heaps O(log n) per insert / O(n)

class MedianFinder {
    PriorityQueue<Integer> lo = // max-heap
        new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> hi = new PriorityQueue<>();
    void add(int num) {
        lo.add(num);
        hi.add(lo.poll());
        if (hi.size() > lo.size()) lo.add(hi.poll());
    }
    double median() {
        if (lo.size() > hi.size()) return lo.peek();
        return (lo.peek() + hi.peek()) / 2.0;
    }
}

// lo = max-heap (negate), hi = min-heap
type MedianFinder struct { lo, hi *IntHeap }

func (m *MedianFinder) Add(num int) {
    heap.Push(m.lo, -num)
    heap.Push(m.hi, -heap.Pop(m.lo).(int))
    if m.hi.Len() > m.lo.Len() {
        heap.Push(m.lo, -heap.Pop(m.hi).(int))
    }
}
func (m *MedianFinder) Median() float64 {
    if m.lo.Len() > m.hi.Len() {
        return float64(-(*m.lo)[0])
    }
    return float64(-(*m.lo)[0]+(*m.hi)[0]) / 2
}

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negate values)
        self.hi = []  # min-heap

    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

use std::collections::BinaryHeap;
use std::cmp::Reverse;
struct MedianFinder {
    lo: BinaryHeap<i32>,            // max-heap
    hi: BinaryHeap<Reverse<i32>>,   // min-heap
}
impl MedianFinder {
    fn add(&mut self, num: i32) {
        self.lo.push(num);
        self.hi.push(Reverse(self.lo.pop().unwrap()));
        if self.hi.len() > self.lo.len() {
            self.lo.push(self.hi.pop().unwrap().0);
        }
    }
    fn median(&self) -> f64 {
        if self.lo.len() > self.hi.len() {
            return *self.lo.peek().unwrap() as f64;
        }
        (*self.lo.peek().unwrap() + self.hi.peek().unwrap().0) as f64 / 2.0
    }
}

class MedianFinder {
    lo: number[] = []; // max-heap (negate values)
    hi: number[] = []; // min-heap
    add(num: number): void {
        heapPush(this.lo, -num);
        heapPush(this.hi, -heapPop(this.lo));
        if (this.hi.length > this.lo.length) {
            heapPush(this.lo, -heapPop(this.hi));
        }
    }
    median(): number {
        if (this.lo.length > this.hi.length) return -this.lo[0];
        return (-this.lo[0] + this.hi[0]) / 2;
    }
}

Use when

Find median from stream
Balance two groups
Sliding window median
Maximize capital (IPO problem)

Watch out

Not balancing heap sizes after each insert
Wrong heap for wrong half
Python heapq is min-heap, negate for max-heap

🔄 Cyclic Sort O(n) / O(1)

List<Integer> cyclicSort(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) {
            int tmp = nums[i];
            nums[i] = nums[correct];
            nums[correct] = tmp;
        } else i++;
    }
    List<Integer> missing = new ArrayList<>();
    for (int j = 0; j < nums.length; j++)
        if (nums[j] != j + 1) missing.add(j + 1);
    return missing;
}

func cyclicSort(nums []int) []int {
    i := 0
    for i < len(nums) {
        correct := nums[i] - 1
        if nums[i] != nums[correct] {
            nums[i], nums[correct] = nums[correct], nums[i]
        } else { i++ }
    }
    var missing []int
    for i, num := range nums {
        if num != i+1 { missing = append(missing, i+1) }
    }
    return missing
}

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct = nums[i] - 1  # where nums[i] should go
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    # Find missing: nums[i] != i + 1
    return [i + 1 for i in range(len(nums)) if nums[i] != i + 1]

fn cyclic_sort(nums: &mut Vec<i32>) -> Vec<i32> {
    let mut i = 0;
    while i < nums.len() {
        let correct = (nums[i] - 1) as usize;
        if nums[i] != nums[correct] {
            nums.swap(i, correct);
        } else { i += 1; }
    }
    (0..nums.len())
        .filter(|&i| nums[i] != i as i32 + 1)
        .map(|i| i as i32 + 1)
        .collect()
}

function cyclicSort(nums: number[]): number[] {
    let i = 0;
    while (i < nums.length) {
        const correct = nums[i] - 1;
        if (nums[i] !== nums[correct]) {
            [nums[i], nums[correct]] = [nums[correct], nums[i]];
        } else i++;
    }
    return nums.flatMap((num, i) =>
        num !== i + 1 ? [i + 1] : []);
}

Use when

Array contains numbers in range [1, n]
Find missing/duplicate number
Find all missing numbers
First missing positive

Watch out

Infinite loop when duplicate exists (check before swap)
Off-by-one between 0-indexed and 1-indexed
Not handling numbers outside valid range

🧩 Subsets & Combinations O(2^n) / O(n)

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    for (int num : nums) {
        int size = result.size();
        for (int i = 0; i < size; i++) {
            List<Integer> copy = new ArrayList<>(result.get(i));
            copy.add(num);
            result.add(copy);
        }
    }
    return result;
}
void combine(int[] nums, int start,
    List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        combine(nums, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

func subsets(nums []int) [][]int {
    result := [][]int{{}}
    for _, num := range nums {
        n := len(result)
        for i := 0; i < n; i++ {
            cp := append([]int{}, result[i]...)
            result = append(result, append(cp, num))
        }
    }
    return result
}
func combine(nums []int, start int,
    path []int, result *[][]int) {
    cp := make([]int, len(path))
    copy(cp, path)
    *result = append(*result, cp)
    for i := start; i < len(nums); i++ {
        combine(nums, i+1, append(path, nums[i]), result)
    }
}

def subsets(nums):
    result = [[]]
    for num in nums:
        result += [curr + [num] for curr in result]
    return result

def combine(nums, start, path, result):
    result.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        combine(nums, i + 1, path, result)
        path.pop()

fn subsets(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut result = vec![vec![]];
    for &num in nums {
        let n = result.len();
        for i in 0..n {
            let mut cp = result[i].clone();
            cp.push(num);
            result.push(cp);
        }
    }
    result
}
fn combine(nums: &[i32], start: usize,
    path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    result.push(path.clone());
    for i in start..nums.len() {
        path.push(nums[i]);
        combine(nums, i + 1, path, result);
        path.pop();
    }
}

function subsets(nums: number[]): number[][] {
    const result: number[][] = [[]];
    for (const num of nums) {
        const n = result.length;
        for (let i = 0; i < n; i++) {
            result.push([...result[i], num]);
        }
    }
    return result;
}
function combine(nums: number[], start: number,
    path: number[], result: number[][]): void {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
        path.push(nums[i]);
        combine(nums, i + 1, path, result);
        path.pop();
    }
}

Use when

Generate all subsets/combinations
Power set
Combination sum
Letter case permutation

Watch out

Not using start index (generating permutations instead)
Not sorting + skipping for duplicate handling
Not making a copy of current path before adding to result

⛓ Linked List Techniques O(n) / O(1)

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1; l1 = l1.next;
        } else {
            curr.next = l2; l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    curr := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            curr.Next = l1; l1 = l1.Next
        } else {
            curr.Next = l2; l2 = l2.Next
        }
        curr = curr.Next
    }
    if l1 != nil { curr.Next = l1 } else { curr.Next = l2 }
    return dummy.Next
}

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

fn merge_two_lists(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    match (l1, l2) {
        (None, r) | (r, None) => r,
        (Some(mut a), Some(mut b)) => {
            if a.val <= b.val {
                a.next = merge_two_lists(a.next.take(), Some(b));
                Some(a)
            } else {
                b.next = merge_two_lists(Some(a), b.next.take());
                Some(b)
            }
        }
    }
}

function mergeTwoLists(
    l1: ListNode | null, l2: ListNode | null
): ListNode | null {
    const dummy = new ListNode(0);
    let curr = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            curr.next = l1; l1 = l1.next;
        } else {
            curr.next = l2; l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = l1 ?? l2;
    return dummy.next;
}

Use when

Merge sorted lists
Partition list
Remove duplicates
Reorder or rearrange list

Watch out

Not using dummy head (complicates edge cases)
Losing tail pointer during merge
Not handling empty list / single node

🏗 Design Patterns Varies (O(1) per op for LRU) / Varies

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    LRUCache(int capacity) { cap = capacity; }
    int get(int key) {
        if (!cache.containsKey(key)) return -1;
        int val = cache.remove(key);
        cache.put(key, val); // move to end
        return val;
    }
    void put(int key, int value) {
        cache.remove(key);
        cache.put(key, value);
        if (cache.size() > cap)
            cache.remove(cache.keySet().iterator().next());
    }
}

type LRUCache struct {
    cap   int
    cache map[int]*list.Element
    order *list.List
}
func (c *LRUCache) Get(key int) int {
    if el, ok := c.cache[key]; ok {
        c.order.MoveToBack(el)
        return el.Value.([2]int)[1]
    }
    return -1
}
func (c *LRUCache) Put(key, value int) {
    if el, ok := c.cache[key]; ok {
        c.order.MoveToBack(el)
        el.Value = [2]int{key, value}
    } else {
        c.cache[key] = c.order.PushBack([2]int{key, value})
        if c.order.Len() > c.cap {
            oldest := c.order.Front()
            delete(c.cache, oldest.Value.([2]int)[0])
            c.order.Remove(oldest)
        }
    }
}

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

use std::collections::HashMap;
struct LRUCache {
    cap: usize,
    map: HashMap<i32, i32>,
    order: Vec<i32>, // use linked list for O(1)
}
impl LRUCache {
    fn get(&mut self, key: i32) -> i32 {
        if let Some(&val) = self.map.get(&key) {
            self.order.retain(|&k| k != key);
            self.order.push(key);
            val
        } else { -1 }
    }
    fn put(&mut self, key: i32, value: i32) {
        self.order.retain(|&k| k != key);
        self.order.push(key);
        self.map.insert(key, value);
        if self.map.len() > self.cap {
            let old = self.order.remove(0);
            self.map.remove(&old);
        }
    }
}

class LRUCache {
    cap: number;
    cache = new Map<number, number>();
    constructor(capacity: number) { this.cap = capacity; }
    get(key: number): number {
        if (!this.cache.has(key)) return -1;
        const val = this.cache.get(key)!;
        this.cache.delete(key);
        this.cache.set(key, val); // move to end
        return val;
    }
    put(key: number, value: number): void {
        this.cache.delete(key);
        this.cache.set(key, value);
        if (this.cache.size > this.cap) {
            this.cache.delete(this.cache.keys().next().value!);
        }
    }
}

Use when

LRU/LFU cache
Min stack / max stack
Iterator design
Custom data structure combining primitives

Watch out

Not maintaining invariants across operations
Forgetting edge cases (capacity=0, empty state)
Not achieving required time complexity for each operation

📐 Segment Tree O(log n) query/update / O(n)

class SegTree {
    int n;
    int[] tree;
    SegTree(int n) { this.n = n; tree = new int[2 * n]; }
    void update(int i, int val) {
        i += n; tree[i] = val;
        for (i /= 2; i > 0; i /= 2)
            tree[i] = tree[2*i] + tree[2*i+1];
    }
    int query(int l, int r) { // [l, r)
        int res = 0;
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if ((l & 1) == 1) res += tree[l++];
            if ((r & 1) == 1) res += tree[--r];
        }
        return res;
    }
}

type SegTree struct { n int; tree []int }

func NewSegTree(n int) *SegTree {
    return &SegTree{n, make([]int, 2*n)}
}
func (s *SegTree) Update(i, val int) {
    i += s.n; s.tree[i] = val
    for i /= 2; i > 0; i /= 2 {
        s.tree[i] = s.tree[2*i] + s.tree[2*i+1]
    }
}
func (s *SegTree) Query(l, r int) int { // [l, r)
    res := 0
    for l, r = l+s.n, r+s.n; l < r; l, r = l/2, r/2 {
        if l&1 == 1 { res += s.tree[l]; l++ }
        if r&1 == 1 { r--; res += s.tree[r] }
    }
    return res
}

class SegTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (2 * n)

    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]

    def query(self, l, r):  # [l, r)
        res, l, r = 0, l + self.n, r + self.n
        while l < r:
            if l & 1: res += self.tree[l]; l += 1
            if r & 1: r -= 1; res += self.tree[r]
            l //= 2; r //= 2
        return res

struct SegTree { n: usize, tree: Vec<i32> }
impl SegTree {
    fn new(n: usize) -> Self {
        Self { n, tree: vec![0; 2 * n] }
    }
    fn update(&mut self, mut i: usize, val: i32) {
        i += self.n; self.tree[i] = val;
        i /= 2;
        while i > 0 {
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1];
            i /= 2;
        }
    }
    fn query(&self, mut l: usize, mut r: usize) -> i32 {
        let mut res = 0;
        l += self.n; r += self.n;
        while l < r {
            if l & 1 == 1 { res += self.tree[l]; l += 1; }
            if r & 1 == 1 { r -= 1; res += self.tree[r]; }
            l /= 2; r /= 2;
        }
        res
    }
}

class SegTree {
    n: number;
    tree: number[];
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(2 * n).fill(0);
    }
    update(i: number, val: number): void {
        i += this.n; this.tree[i] = val;
        for (i = Math.floor(i / 2); i > 0; i = Math.floor(i / 2))
            this.tree[i] = this.tree[2*i] + this.tree[2*i+1];
    }
    query(l: number, r: number): number { // [l, r)
        let res = 0;
        for (l += this.n, r += this.n; l < r;
             l = Math.floor(l/2), r = Math.floor(r/2)) {
            if (l & 1) res += this.tree[l++];
            if (r & 1) res += this.tree[--r];
        }
        return res;
    }
}

Use when

Range sum/min/max with updates
Count in range queries
Interval scheduling
Need better than O(n) per query

Watch out

Off-by-one in tree indexing
Not propagating lazy updates
Using segment tree when prefix sum or BIT suffices

🔎 String Matching O(n + m) / O(m)

int kmpSearch(String text, String pattern) {
    int[] lps = new int[pattern.length()];
    for (int i = 1, len = 0; i < pattern.length(); ) {
        if (pattern.charAt(i) == pattern.charAt(len))
            lps[i++] = ++len;
        else if (len > 0) len = lps[len - 1];
        else i++;
    }
    for (int i = 0, j = 0; i < text.length(); ) {
        if (text.charAt(i) == pattern.charAt(j)) { i++; j++; }
        if (j == pattern.length()) return i - j;
        if (i < text.length()
            && text.charAt(i) != pattern.charAt(j)) {
            j = j > 0 ? lps[j - 1] : 0;
            if (j == 0 && text.charAt(i) != pattern.charAt(0)) i++;
        }
    }
    return -1;
}

func kmpSearch(text, pattern string) int {
    lps := make([]int, len(pattern))
    for i, length := 1, 0; i < len(pattern); {
        if pattern[i] == pattern[length] {
            length++; lps[i] = length; i++
        } else if length > 0 {
            length = lps[length-1]
        } else { i++ }
    }
    i, j := 0, 0
    for i < len(text) {
        if text[i] == pattern[j] { i++; j++ }
        if j == len(pattern) { return i - j }
        if i < len(text) && text[i] != pattern[j] {
            if j > 0 { j = lps[j-1] } else { i++ }
        }
    }
    return -1
}

def kmp_search(text, pattern):
    # Build failure function
    lps = [0] * len(pattern)
    length, i = 0, 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            i += 1
    # Search
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1; j += 1
        if j == len(pattern):
            return i - j  # match found
        elif i < len(text) and text[i] != pattern[j]:
            j = lps[j - 1] if j else 0
            if not j: i += 1
    return -1

fn kmp_search(text: &str, pattern: &str) -> i32 {
    let (t, p) = (text.as_bytes(), pattern.as_bytes());
    let mut lps = vec![0usize; p.len()];
    let (mut i, mut len) = (1, 0);
    while i < p.len() {
        if p[i] == p[len] { len += 1; lps[i] = len; i += 1; }
        else if len > 0 { len = lps[len - 1]; }
        else { i += 1; }
    }
    let (mut i, mut j) = (0usize, 0usize);
    while i < t.len() {
        if t[i] == p[j] { i += 1; j += 1; }
        if j == p.len() { return (i - j) as i32; }
        if i < t.len() && t[i] != p[j] {
            if j > 0 { j = lps[j - 1]; } else { i += 1; }
        }
    }
    -1
}

function kmpSearch(text: string, pattern: string): number {
    const lps = new Array(pattern.length).fill(0);
    for (let i = 1, len = 0; i < pattern.length; ) {
        if (pattern[i] === pattern[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else i++;
    }
    for (let i = 0, j = 0; i < text.length; ) {
        if (text[i] === pattern[j]) { i++; j++; }
        if (j === pattern.length) return i - j;
        if (i < text.length && text[i] !== pattern[j]) {
            if (j) j = lps[j - 1]; else i++;
        }
    }
    return -1;
}

Use when

Find pattern in text
Count pattern occurrences
Multiple pattern search
Longest prefix which is also suffix

Watch out

Not handling hash collisions (Rabin-Karp)
Wrong failure function construction (KMP)
Using naive O(nm) when O(n+m) is needed