Algo Cheat Sheet

✅ Part 1: Two Pointers

---

🔸 Pattern 1: Two Pointers – Opposite Ends (Single Input)

When to use: Use when searching or comparing from both ends of a sorted array or palindromic structure.

Template:

int left = 0, right = arr.length - 1;
while (left < right) {
    if (CONDITION) {
        left++;
    } else {
        right--;
    }
}

Time: O(n) Space: O(1)

Edge Cases:

• Empty array → check arr.length == 0
• Odd/even number of elements → watch for left == right behavior

Examples:

• Check if array can form palindrome
• Two Sum II (sorted input)
• Container With Most Water

---

🔸 Pattern 2: Two Pointers – Parallel Arrays (Two Inputs)

When to use: Use to merge sorted arrays or synchronize traversals over two inputs.

Template:

int i = 0, j = 0;
while (i < arr1.length && j < arr2.length) {
    if (CONDITION) {
        i++;
    } else {
        j++;
    }
}

Time: O(n + m) Space: O(1)

Edge Cases:

• One input empty → handle gracefully
• Uneven lengths

Examples:

• Merge two sorted arrays
• Intersection of Two Arrays
• Comparing character streams

---

✅ Part 2: Sliding Window

---

🔸 Pattern: Fixed/Growing Window (Single Input)

When to use: When you need to process contiguous subarrays or substrings with a running total, count, or frequency. Especially useful for problems with "at most", "exactly", or "maximum/minimum subarray length".

---

Template: Growing + Shrinking Window

int left = 0, curr = 0, ans = 0;

for (int right = 0; right < arr.length; right++) {
    curr += arr[right];  // or add to map/frequency/etc

    while (WINDOW_CONDITION_BROKEN) {
        curr -= arr[left];  // or remove from map
        left++;
    }

    ans = Math.max(ans, right - left + 1);  // or update condition
}

---

Time: O(n) Space: O(1) to O(n) (e.g., for HashMap if tracking frequency)

---

Edge Cases:

• All elements valid → window never shrinks
• Watch off-by-one: right - left + 1 is window size
• Negative numbers may break assumptions → usually sliding window assumes non-negativity

---

✅ Common Variations

🔹 Minimum Window Substring (Dynamic + HashMap)

Map<Character, Integer> need = ..., window = ...;
int valid = 0, left = 0, right = 0;

while (right < s.length()) {
    char c = s.charAt(right);
    right++;
    // update window, valid

    while (valid == need.size()) {
        // update answer
        char d = s.charAt(left);
        left++;
        // update window, valid
    }
}

🔹 Fixed-size window (e.g., find max average of k elements)

double sum = 0;
for (int i = 0; i < arr.length; i++) {
    sum += arr[i];
    if (i >= k - 1) {
        max = Math.max(max, sum / k);
        sum -= arr[i - k + 1];
    }
}

---

Examples:

• Longest Substring Without Repeating Characters
• Minimum Size Subarray Sum
• Max Consecutive Ones III
• Permutation in String
• Max Sum of Fixed-Length Subarray

---

✅ Part 3: Prefix Sum

---

🔸 Pattern: Prefix Sum (1D)

When to use: When you need to quickly compute the sum of any subarray in O(1) time after O(n) preprocessing.

---

Template: Build Prefix Sum Array

int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}

// sum of arr[i..j] = prefix[j + 1] - prefix[i]

---

Time:

• Build: O(n)
• Query: O(1) Space: O(n)

---

Edge Cases:

• Off-by-one: prefix is usually one element longer
• Subarray start at 0 → use prefix[j + 1]
• Negative numbers are fine

---

Examples:

• Subarray Sum Equals K (with HashMap)
• Range Sum Query (static array)
• Maximum Subarray (Kadane can be better)
• Find Pivot Index

---

🔸 Bonus: With HashMap – Subarrays With Target Sum

Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);
int curr = 0, ans = 0;

for (int num : arr) {
    curr += num;
    ans += prefixCount.getOrDefault(curr - k, 0);
    prefixCount.put(curr, prefixCount.getOrDefault(curr, 0) + 1);
}

---

🔸 Pattern: Prefix Sum (2D)

When to use: For quick lookup of rectangle sums in a matrix.

---

Template:

int[][] prefix = new int[rows + 1][cols + 1];
for (int i = 1; i <= rows; i++) {
    for (int j = 1; j <= cols; j++) {
        prefix[i][j] = matrix[i - 1][j - 1]
                     + prefix[i - 1][j]
                     + prefix[i][j - 1]
                     - prefix[i - 1][j - 1];
    }
}

// sum of rectangle (r1, c1) to (r2, c2) is:
int sum = prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1];

Time:

• Build: O(m * n)
• Query: O(1) Space: O(m * n)

---

Examples:

• Range Sum Query 2D
• Count Submatrices with Target Sum
• Max Sum Submatrix No Larger Than K

---

✅ Part 4: Binary Search

---

🔸 Pattern: Classic Binary Search (Exact Target)

When to use: To find the index of a target element in a sorted array (increasing or decreasing).

---

Template:

int left = 0, right = arr.length - 1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

return -1; // not found

---

Time: O(log n) Space: O(1)

---

Edge Cases:

• Overflow → use mid = left + (right - left) / 2
• Duplicates → may need leftmost/rightmost variant
• Infinite loop if you don’t update pointers correctly

---

🔸 Pattern: Leftmost Insertion Point (Lower Bound)

When to use: To find the first index where arr[i] >= target. Used in lower bound logic, or custom binary search.

---

Template:

int left = 0, right = arr.length;

while (left < right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] >= target) right = mid;
    else left = mid + 1;
}

return left;

---

🔸 Pattern: Rightmost Insertion Point (Upper Bound)

When to use: To find the first index where arr[i] > target, or last index <= target.

---

Template:

int left = 0, right = arr.length;

while (left < right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] > target) right = mid;
    else left = mid + 1;
}

return left;

---

🔸 Pattern: Binary Search on Answer (Greedy Check)

When to use: You can’t directly binary search the array, but you can guess a value (e.g., minimum/max value), then check feasibility using a helper function.

---

Template: Min Value That Works

int left = MIN_POSSIBLE, right = MAX_POSSIBLE;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (check(mid)) right = mid - 1;
    else left = mid + 1;
}

return left;

Template: Max Value That Works

int left = MIN_POSSIBLE, right = MAX_POSSIBLE;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (check(mid)) left = mid + 1;
    else right = mid - 1;
}

return right;

---

Examples:

• Classic: Binary Search, Search Insert Position

• Leftmost/rightmost: First/Last Occurrence in Sorted Array

• Search on Answer:

  • Split Array Largest Sum
  • Koko Eating Bananas
  • Capacity to Ship Packages
  • Aggressive Cows (classic)

---

✅ Part 5: DFS & BFS (Traversal Patterns)

---

🔸 Pattern: DFS (Recursive)

When to use: For exploring depth-first in trees, graphs, or matrices. Easy to use when recursion is natural or depth is manageable.

---

Template (Tree or Graph):

void dfs(Node node, Set<Node> visited) {
    if (node == null || visited.contains(node)) return;

    visited.add(node);
    // do logic

    for (Node neighbor : node.neighbors) {
        dfs(neighbor, visited);
    }
}

Time: O(N + E) (nodes + edges) Space: O(N) recursion + visited set

---

🔸 Pattern: DFS (Iterative)

When to use: To avoid recursion stack overflow or make DFS logic more explicit.

---

Template:

Stack<Node> stack = new Stack<>();
Set<Node> visited = new HashSet<>();

stack.push(start);
visited.add(start);

while (!stack.isEmpty()) {
    Node node = stack.pop();
    // do logic

    for (Node neighbor : node.neighbors) {
        if (!visited.contains(neighbor)) {
            stack.push(neighbor);
            visited.add(neighbor);
        }
    }
}

---

🔸 Pattern: BFS (Queue-Based)

When to use: When you want the shortest path in an unweighted graph, or level-by-level traversal in a tree/matrix.

---

Template:

Queue<Node> queue = new LinkedList<>();
Set<Node> visited = new HashSet<>();

queue.add(start);
visited.add(start);

while (!queue.isEmpty()) {
    int size = queue.size();  // optional: for level tracking
    for (int i = 0; i < size; i++) {
        Node node = queue.poll();
        // do logic

        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.add(neighbor);
            }
        }
    }
}

---

✅ Matrix-Specific DFS/BFS (e.g., islands)

int[][] dirs = {{0,1},{1,0},{-1,0},{0,-1}};

void dfs(int r, int c, boolean[][] visited, char[][] grid) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return;
    if (visited[r][c] || grid[r][c] == '0') return;

    visited[r][c] = true;
    for (int[] dir : dirs) {
        dfs(r + dir[0], c + dir[1], visited, grid);
    }
}

---

Edge Cases:

• Don’t forget to mark visited before pushing/enqueuing (avoids cycles)
• Infinite loops on cycles if visited not used
• DFS stack overflow on deep recursion → use iterative

---

Examples:

• Tree: Binary Tree Inorder/Postorder
• Graph: Clone Graph, Connected Components
• Matrix: Number of Islands, Flood Fill, Rotting Oranges
• Shortest Path: Word Ladder (BFS), Maze Escape

---

✅ Part 6: Dynamic Programming (DP)

---

🔸 When to Use:

If you can:

1. Break a problem into overlapping subproblems, and
2. Define a state that can be reused, → it's a DP problem.

---

🔹 DP Types

Type	Approach	Example Problems
Top-Down (Memoization)	Recursion + caching	Fibonacci, Grid Paths
Bottom-Up (Tabulation)	Iterative DP table	Coin Change, Knapsack
Space-Optimized	1D or few vars	House Robber, Climbing Stairs

---

🔸 Top-Down (Memoization)

Template:

Map<State, Integer> memo = new HashMap<>();

int dp(State s) {
    if (BASE_CASE) return 0;
    if (memo.containsKey(s)) return memo.get(s);

    int result = ... // recursion
    memo.put(s, result);
    return result;
}

Time: Depends on number of states × branching Space: O(#states) + recursion stack

---

Example: Fibonacci (Top-Down)

Map<Integer, Integer> memo = new HashMap<>();

int fib(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);

    int val = fib(n - 1) + fib(n - 2);
    memo.put(n, val);
    return val;
}

---

🔸 Bottom-Up (Tabulation)

Template:

int[] dp = new int[n + 1];
dp[0] = BASE;
for (int i = 1; i <= n; i++) {
    dp[i] = recurrence(dp[i-1], dp[i-2], ...);
}
return dp[n];

Time: O(n) Space: O(n) (can often reduce to O(1))

---

Example: Climbing Stairs (Bottom-Up)

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

---

🔸 2D DP Table (Grid Problems)

Template:

int[][] dp = new int[m][n];
dp[0][0] = ...;

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    }
}

---

🔸 Knapsack (0/1)

int[][] dp = new int[n + 1][W + 1];

for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        if (weights[i-1] <= w) {
            dp[i][w] = Math.max(
                dp[i-1][w],
                dp[i-1][w - weights[i-1]] + values[i-1]
            );
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

---

🔸 Common Problems to Master

Problem	Pattern
Climbing Stairs	1D bottom-up
House Robber	1D, exclude adjacent
Longest Increasing Subsequence	O(n²) or O(n log n)
Edit Distance	2D table
Word Break	DP + HashSet
Coin Change	Min # coins, bottom-up
Palindrome Partitioning	DP + recursion
Target Sum / Subset Sum	DP on sum differences

---

Edge Cases / Tips:

• Identify the state clearly (often index, remaining sum, etc.)
• Carefully handle base cases
• Use memoization if the recursion tree repeats work
• Use bottom-up if you want tighter control of space

---

✅ Part 7: Backtracking

---

🔸 When to Use:

Use Backtracking when:

• You need to explore all possible options, and
• You want to prune invalid paths early to avoid extra work.

It’s basically DFS + undo step.

---

🔸 General Template

void backtrack(PartialSolution state, Input input) {
    if (BASE_CASE) {
        addToResult(state);
        return;
    }

    for (option in inputOptions) {
        if (!isValid(option)) continue;

        state.add(option);       // choose
        backtrack(state, input); // explore
        state.remove(option);    // un-choose (backtrack)
    }
}

---

🔸 Time/Space:

• Time: O(branching^depth)
• Space: O(depth) recursion + optional result list

---

🔹 Common Variations

---

1. Subsets (All combinations)

void dfs(int start, List<Integer> path) {
    result.add(new ArrayList<>(path));

    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        dfs(i + 1, path);
        path.remove(path.size() - 1);
    }
}

Example: subsets([1,2,3]) → [[], [1], [1,2], [1,2,3], ...]

---

2. Permutations (All orderings)

void dfs(List<Integer> path, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        used[i] = true;
        path.add(nums[i]);
        dfs(path, used);
        used[i] = false;
        path.remove(path.size() - 1);
    }
}

Example: permute([1,2,3])

---

3. Combination Sum (Repeated choices)

void dfs(int start, int target, List<Integer> path) {
    if (target == 0) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > target) continue;

        path.add(candidates[i]);
        dfs(i, target - candidates[i], path); // not i+1, because we can reuse
        path.remove(path.size() - 1);
    }
}

---

4. N-Queens / Sudoku (2D constraints)

Use isValid(row, col) to check constraints (e.g., no same row/col/diag), and recursively fill row by row or cell by cell.

---

Edge Cases / Tips:

• Always do .add() → recursive call → .remove() in that exact order
• Use Set, boolean[], or pruning (e.g., continue if used)
• When dealing with strings/2D boards, clone or backtrack carefully
• Use return boolean if you're looking for a single valid result

---

✅ Classic Problems

Problem	Pattern
Subsets	Backtrack with index
Permutations	Track used elements
Combination Sum	Allow reuse of numbers
Word Search	DFS with backtrack on grid
Sudoku Solver	Try all valid digits
N-Queens	Place 1 queen per row

---

✅ Part 8: Greedy Algorithms

---

🔸 When to Use:

Use Greedy when:

• You can make a locally optimal choice at each step,
• That choice leads to a globally optimal solution,
• Or the problem says: “maximize”, “minimize”, “smallest/largest” with sorting or greedy picking.

---

🔹 General Greedy Strategy

// Sort based on greedy criteria
Arrays.sort(input, (a, b) -> greedyComparator);

// Iterate and greedily build solution
for (type item : input) {
    if (validToPick(item)) {
        // choose item
    }
}

Time: Often O(n log n) due to sorting Space: Often O(1) or minimal

---

🔸 Common Patterns

---

1. Interval Scheduling (Meeting Rooms, Erase Overlap)

// Sort by end time
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

int count = 0, end = Integer.MIN_VALUE;

for (int[] interval : intervals) {
    if (interval[0] >= end) {
        count++;
        end = interval[1];
    }
}

Example: Max number of non-overlapping intervals

---

2. Minimum Platforms / Merge Intervals

• Sort start and end times separately
• Use two pointers or min-heap to track overlaps

---

3. Jump Game (Greedy Reach)

int farthest = 0;
for (int i = 0; i <= farthest; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (farthest >= nums.length - 1) return true;
}
return false;

---

4. Task Scheduling (Greedy with Sorting)

// Sort tasks by deadline, difficulty, etc.
Arrays.sort(tasks, (a, b) -> ...);

// Greedily assign time/resource

---

5. Huffman Encoding / Fractional Knapsack

• Use a priority queue (min-heap / max-heap)
• Pick best ratio/value first

---

🔸 Greedy vs DP?

Check	If Yes, Use Greedy
Can you sort and build solution step-by-step?	✅
Local choices affect future too much?	❌ (Use DP)
Does the problem resemble a classical greedy one?	✅
Need all possible combinations?	❌ (Use Backtracking or DP)

---

✅ Common Greedy Problems

Problem	Strategy
Jump Game I / II	Greedy max reach
Merge Intervals	Sort + greedy merge
Erase Overlap Intervals	Sort by end
Partition Labels	Track farthest index
Task Scheduler	Frequency + greedy
Candy Distribution	Two passes (L→R, R→L)

---

Edge Cases / Tips:

• Sorting direction matters (e.g., ascending vs descending)
• PriorityQueue is often useful for greedy
• Careful with tie-breakers in sort logic

---

✅ Part 9: Union-Find (Disjoint Set Union - DSU)

---

🔸 When to Use:

Use Union-Find when solving problems involving connected components, such as:

• Graphs with undirected connections
• Cycle detection
• MST (Kruskal’s algorithm)
• “Number of islands” in grid with union ops

---

🔹 Template: Union-Find (with Path Compression & Union by Rank)

class UnionFind {
    int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // Path compression
        return parent[x];
    }

    public void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;

        if (rank[px] > rank[py]) parent[py] = px;
        else if (rank[px] < rank[py]) parent[px] = py;
        else {
            parent[py] = px;
            rank[px]++;
        }
    }
}

---

✅ Common Union-Find Problems

Problem	Pattern
Connected Components in Graph	Union-Find
Redundant Connection	Cycle Detection with Union-Find
Number of Provinces	Union connected cities
Accounts Merge	Union by owner
Satisfiability of Equality Equations	Union letters

---

Tips:

• Use Map<String, String> for string-based Union-Find (e.g., email merging)
• Be sure to compress the path in find() to avoid TLE
• rank[] helps avoid long chains

---

✅ Part 7: Stack

🔸 When to Use

Use a Stack when:

• You need Last-In-First-Out (LIFO) processing:
  • Matching symbols (e.g., parentheses)
  • Tracking state (e.g., minimum values)
  • Reverse-order processing (e.g., evaluate expressions)

---

🔸 General Template

Stack<Type> stack = new Stack<>();
for (Type element : input) {
    if (pushCondition(element)) stack.push(element);
    else if (popCondition(element)) {
        Type top = stack.pop();
        // Process top and element
    }
}

• Time: O(n)
• Space: O(n)

---

🔸 Edge Cases

• Empty Stack: Use stack.isEmpty() before pop() or peek().
• Unbalanced Input: Ensure closing brackets match opening ones.
• Invalid Input: Validate tokens (e.g., in expression parsing).

---

🔸 Common Variations

1. Matching/Balancing (Valid Parentheses)

Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
    if (c == '(' || c == '{' || c == '[') stack.push(c);
    else if (stack.isEmpty() || !matches(stack.pop(), c)) return false;
}
return stack.isEmpty();

boolean matches(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

2. Min Stack (Constant-Time Min)

class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) minStack.push(val);
    }

    void pop() {
        if (stack.pop().equals(minStack.peek())) minStack.pop();
    }

    int top() { return stack.peek(); }
    int getMin() { return minStack.peek(); }
}

---

🔸 Time/Space Complexity

Problem	Time	Space
Valid Parentheses	O(n)	O(n)
Min Stack	O(1)	O(n)

---

🔸 Tips

• Prefer Deque (e.g., ArrayDeque) in Java for better performance.
• Use Map or helper methods for symbol matching.
• See Monotonic Stack (Part 13) for advanced usage.

---

✅ Common Stack Problems

Problem	Strategy	Difficulty
Valid Parentheses	Push opening, match closing	Easy
Simplify Path	Push dirs, pop for ..	Medium
Min Stack	Use two stacks	Medium
Evaluate Reverse Polish Notation	Push operands, pop for operators	Medium
Basic Calculator	Use stack for numbers/operators	Hard

✅ Part 8: Linked List

🔸 When to Use

Use Linked List manipulation when:

• Traversing, modifying, or rearranging a singly/doubly linked list
• Problems involve pointer manipulation (reverse, merge, cycle detect)

---

🔸 General Template

ListNode dummy = new ListNode(0), curr = dummy;
while (condition) {
    // Manipulate pointers (e.g., curr.next = ...)
    curr = curr.next;
}
return dummy.next;

• Time: O(n)
• Space: O(1) for in-place, O(n) with extra space

---

🔸 Edge Cases

• Empty List: head == null
• Single Node: Handle separately
• Cycle Detection: Use fast/slow pointers
• Invalid Input: Check bounds, k > length

---

🔸 Common Variations

1. Merging Lists (Merge Two Sorted Lists)

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;
}

2. Reversing Segments (Reverse Linked List II)

ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(0), prev = dummy;
    dummy.next = head;
    for (int i = 1; i < m; i++) prev = prev.next;
    ListNode curr = prev.next;
    for (int i = m; i < n; i++) {
        ListNode next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }
    return dummy.next;
}

3. LRU

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

---

🔸 Time/Space Complexity

Problem	Time	Space
Merge Two Sorted Lists	O(n+m)	O(1)
Reverse Linked List II	O(n)	O(1)

---

🔸 Tips

• Use a dummy node for edge case handling
• Fast-slow pointers = cycle detection
• Preserve .next before link updates
• Use HashMap for problems with random pointers

---

✅ Common Linked List Problems

Problem	Strategy	Difficulty
Linked List Cycle	Fast-slow pointers	Easy
Add Two Numbers	Add digits w/ carry	Medium
Merge Two Sorted Lists	Merge sorted via comparison	Easy
Copy List with Random Pointer	Interleave or use HashMap	Medium
Reverse Linked List II	Reverse segment w/ pointers	Medium
Reverse Nodes in k-Group	Reverse k-nodes iteratively/recursively	Hard
Remove Nth Node From End of List	Fast-slow to locate node	Medium
Remove Duplicates from Sorted List II	Skip duplicates	Medium
Rotate List	Count nodes, adjust tail and head	Medium
Partition List	Build two lists, merge	Medium
LRU Cache	Doubly linked list + HashMap	Medium

---

✅ Part 10: Trie (Prefix Tree)

---

🔸 When to Use:

Use Trie when:

• You need efficient prefix-based searching
• You’re solving word dictionary, autocomplete, or string search problems

---

🔹 Template: TrieNode Class

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord = false;
}

🔹 Template: Trie Class

class Trie {
    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        TrieNode node = find(word);
        return node != null && node.isWord;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private TrieNode find(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) return null;
            node = node.children.get(c);
        }
        return node;
    }
}

---

✅ Common Trie Problems

Problem	Pattern
Implement Trie (Prefix Tree)	Trie structure
Word Dictionary (with . wildcard)	DFS + Trie
Replace Words	Trie + String.replace
Longest Word in Dictionary	Trie + BFS
Concatenated Words	Trie + DFS

---

Tips:

• Use DFS/BFS for wildcard or deep word search
• You can store additional data at nodes (e.g., word count, index)
• For large alphabets, use Map; for lowercase a–z, use TrieNode[26]

---

✅ Part 11: Heaps / Priority Queue

---

🔸 When to Use:

Use PriorityQueue when you want to:

• Always get the min or max element quickly
• Solve top-k, merge k sorted lists, or scheduling problems

---

🔹 Min-Heap (Default in Java)

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

🔹 Max-Heap

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

---

🔹 Template: Top K Elements

PriorityQueue<Integer> heap = new PriorityQueue<>();

for (int num : nums) {
    heap.offer(num);
    if (heap.size() > k) heap.poll();  // maintain k elements
}

List<Integer> result = new ArrayList<>(heap);  // top k smallest

---

✅ Common Heap Problems

Problem	Strategy
Kth Largest Element	Min-heap of size k
Merge K Sorted Lists	Min-heap of list heads
Top K Frequent Elements	Heap on frequency
Task Scheduler	Max-heap on frequency
Median from Data Stream	Two heaps (min & max)

---

🔸 Tips:

• Use custom comparator for objects: new PriorityQueue<>((a, b) -> a.cost - b.cost)
• heap.poll() → remove min/max
• heap.peek() → view min/max

---

✅ Part 12: Monotonic Stack & Queue

---

🔸 When to Use:

Use Monotonic Stack/Queue when:

• You need to maintain increasing/decreasing order
• You want to efficiently find next/previous greater/smaller elements
• Solving problems like histograms, sliding window max, stock span

---

🔹 Monotonic Stack (Increasing)

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < arr.length; i++) {
    while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
        stack.pop();
    }
    stack.push(i);
}

---

✅ Common Stack Problems

Problem	Strategy
Next Greater Element	Monotonic decreasing stack
Daily Temperatures	Index stack + while loop
Largest Rectangle in Histogram	Monotonic increasing stack
Stock Span	Maintain stack of indices
Remove K Digits	Greedily remove digits using stack

---

🔹 Monotonic Queue (Sliding Window Max)

Deque<Integer> deque = new LinkedList<>();

for (int i = 0; i < arr.length; i++) {
    // remove smaller elements from the back
    while (!deque.isEmpty() && arr[deque.peekLast()] < arr[i])
        deque.pollLast();

    deque.offerLast(i);

    // remove out-of-window indices
    if (deque.peekFirst() <= i - k)
        deque.pollFirst();

    if (i >= k - 1)
        result.add(arr[deque.peekFirst()]);
}

---

Tips:

• Store indices in the stack/queue, not values, for flexibility
• For window problems, always remove out-of-window elements first
• Watch for strict vs non-strict comparisons (< vs <=)

---

Would you like to finish with Bit Manipulation + Math/Number Tricks, or should we generate a printable version or condensed reference for everything we’ve covered?

Great — let’s wrap up with Bit Manipulation and Math/Number Tricks, which are lightweight but often show up in competitive coding and tech interviews.

---

✅ Part 13: Bit Manipulation

---

🔸 When to Use:

Use when dealing with:

• Sets, toggles, parity checks
• Optimizing space for small-range integers
• Problems involving powers of 2 or XOR

---

🔹 Common Bit Tricks

1. Check if number is even/odd

if ((n & 1) == 0) // even

2. Get ith bit

int bit = (n >> i) & 1;

3. Set ith bit

n = n | (1 << i);

4. Clear ith bit

n = n & ~(1 << i);

5. Toggle ith bit

n = n ^ (1 << i);

6. Check if n is a power of 2

(n > 0) && ((n & (n - 1)) == 0)

7. Count set bits (Brian Kernighan’s Algo)

int count = 0;
while (n != 0) {
    n = n & (n - 1);
    count++;
}

---

✅ Common Bit Problems

Problem	Strategy
Single Number (appears once)	Use XOR
Power of Two	n > 0 && (n & (n - 1)) == 0
Subsets (via bits)	Iterate from 0 to 2^n
Bitwise AND/OR/XOR Ranges	Bit patterns & shifts

---

✅ Part 14: Math & Number Tricks

---

🔸 When to Use:

Useful in:

• Modulo arithmetic
• Counting problems
• Prime checks
• Digit-based problems (reverse, sum, etc.)

---

🔹 Modular Arithmetic

// Avoid negative modulo
int result = ((a % MOD) + MOD) % MOD;

---

🔹 GCD & LCM

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

---

🔹 Fast Power (Binary Exponentiation)

long pow(long a, long b, int mod) {
    long res = 1;
    a %= mod;
    while (b > 0) {
        if ((b & 1) == 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

---

🔹 Primes (Sieve of Eratosthenes)

boolean[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

---

✅ Common Math Problems

Problem	Strategy
Reverse Integer	Modulo and divide
Palindrome Number	Rebuild from digits
Count Primes	Sieve of Eratosthenes
Pow(x, n)	Binary Exponentiation
GCD/LCM	Euclidean algorithm

---

✅ Final Tips for Math + Bit

• Watch out for integer overflow in Java (long when needed)
• Use % MOD when working with big numbers or DP counts
• Binary search, greedy, and DP often involve math tricks subtly

---

✅ That completes the full structured algorithm cheat sheet series! Would you like a:

• ✅ Printable PDF version or markdown export?
• ✅ Searchable index or quick-reference?
• ✅ Problem list mapped to each pattern?

Let me know how you'd like to finalize and use this.